HTree
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/11 15:52 UTC 版)
HTree はLinuxのファイルシステムで使われている、B木に似た木構造を用いたディレクトリインデックスである。HTreeの深さは1種か2種の値で一定であり、ファン・アウト数が大きいのが特徴である。ファイル名のハッシュを用いる構造であり、平衡を取る必要はない[1]。単に、標準的なB木のアルゴリズムを応用すると、ハッシュの衝突が生じた場合に、複数の葉ノードとインデックスブロックがオーバーフローを生じるため、HTreeではその対処を行っている。HTreeを用いたインデックスは、Linuxのファイルシステムであるext3やext4で用いられ、Linuxカーネル 2.5.40 に組み込まれている[2]。HTreeのインデックスはLinux ext2 ベースのファイルシステムが数千ファイルで実質的に制限されていた問題を、ディレクトリごとに数千万ファイルを扱える程に改善した。
歴史
HTreeによるインデックスのデータ構造とアルゴリズムは2000年に Daniel Phillips によって開発され、2001年2月に ext2 ファイルシステム用に実装された。2002年には、Christopher LiとAndrew Mortonがジャーナリングファイルシステムをベースとした衝突一貫性を、2.5系のカーネルのext3ファイルシステムへのポートに追加した。 さらに軽微な改良が加えられ、HTreeはLinux 3.x.xカーネルシリーズのext4で引き続き使用されている。
使用例
- ext2 HTreeインデックスはもともと ext2 用に開発されたが、結局パッチは公式ブランチには作られなかった。dir_index機能は、ext2ファイルシステムを作成するときに有効にできる一方で、ext2コードはext2ファイルシステムでは動作しません。
- ext3 HTreeインデックスは、dir_index機能が有効な場合にext3で利用可能である。
- ext4 HTreeインデックスはext4ではデフォルトで有効になっている。この機能は、Linuxカーネル2.6.23で実装された。HTreeインデックスは、ファイルがInodeに格納されている5つ以上のエクステントを必要とする場合、ファイルエクステントにも使用されます。
PHTree
PHTree (Physically stable HTree) は、HTreeの後継として開発された[3]。Write multiplication以外のHTreeの既知の問題をすべて修正したHTreeである。PHTreeはTux3ファイルシステムで使用されている[4]。
出典
- ^ Mingming Cao. “Directory indexing”. Features found in Linux 2.6. 2018年2月4日閲覧。
- ^ tytso@mit.edu. “Add ext3 indexed directory (htree) support”. 2018年2月4日閲覧。
- ^ http://phunq.net/pipermail/tux3/2013-January/000026.html[信頼性要検証]
- ^ “Archived copy”. 2015年1月13日時点のオリジナルよりアーカイブ。2014年12月28日閲覧。
外部リンク
- Ext2 のディレクトリインデックス (HTreeのデータ構造の説明) at Archive.is (archived 2013-04-15)
- HTree
- HPDD Wiki - 並列ディレクトリの高度な設計
H木
(HTree から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/30 05:39 UTC 版)
H木、H treeまたはH-Tree はフラクタル図形の1つであり、直線の両端に、その長さの1/√2の長さの垂線を追加し続けることによって構成される図形である。繰り返しパターンがアルファベットの "H" に似ているため、H木と呼ばれる。ハウスドルフ次元は2であり、矩形内の任意の点に対し、十分近いH木上の点が存在する。任意のステップにおいて、中心から端点までの距離がすべて等しい性質を利用し、VLSI設計とマイクロ波工学で用いられている。
構成
H木は、任意の長さの線分を元に、「その線分の両端に垂直な1/√2の長さの2本の線分を追加する」という処理を繰り返すことで構成できる[1]。
また、白銀比である1:√2の長方形から開始し、長辺を2等分し、その重心を直線で結ぶという処理でも構築できる。1:√2 = √2/2:1であるため、分割された長方形もまた白銀比の長方形である。他の比で表される長方形でも同様の処理は可能であるが、白銀比でない長方形では、奇数ステップと偶数ステップでは重心間の距離の比が一定ではない。
性質
H木は自己相似図形（フラクタル図形）であり、そのハウスドルフ次元は2である[2]。
矩形（白銀比の長方形）内の任意の点に対し、十分近いH木上の点が存在する。しかし、全ての点が「含まれる」わけではなく、例えば1ステップ目の線分に対する垂直二等分線はH木に含まれない。
応用
VLSIの設計において、H木は木のノード数に比例する面積を使用する、完全二分木のレイアウトとして用いられる[3]。また、H木の形は長方形内に効率的にグラフを描画可能であり[4]、巡回セールスマン問題の距離の自乗和が大きくなる点の集合としても用いられる[5]。
H木は全てのノードまでの距離が等しいため、中央に発振子を置き、葉ノードの位置に素子を置くことで、クロックの伝播遅延を揃えることができる[6]。そして、VLSIマルチプロセッサの相互接続ネットワークとしても用いられる[7]。同様の理由で、H木は各マイクロストリップアンテナが受信した信号の伝播遅延を揃えることができるため、マイクロストリップアンテナアレイに用いられる。
これまで述べたような2次元平面上のH木は、H木の平面に対して垂直な方向に線分を加えるように変更することで、3次元構造へと一般化することが可能である[8]。この処理により構成される3次元H木は、ハウスドルフ次元が3である。2次元H木と3次元H木は、フォトニック結晶やメタマテリアルにおいて artificial electromagnetic atoms を構成することが知られており、マイクロ波工学において潜在的な用途を有する可能性がある。
関連する集合
H木はフラクタルキャノピーの1つであり、隣接する線分間の角度は常に180度である。矩形内の任意の点に対して十分近づくという性質を持つため、「曲線」ではないが、空間充填曲線に似ている。
位相幾何学的には、H木にはデンドロイドと同様の性質があるといえる。しかし、デンドロイドは閉集合である必要があるため、閉集合ではないH木はデンドロイドではない。
マンデルブロ木は、より自然な見た目を生成するために、H木の位置から僅かにずれた位置に、線分の代わりに長方形を使用するフラクタル図形である。長方形同士が重ならないようにするために、スケールを1/√2より小さくする必要がある[9]。
脚注
- ^ H-Fractal, Sándor Kabai, The Wolfram Demonstrations Project.
- ^ Kaloshin & Saprykina (2012).
- ^ Leiserson (1980).
- ^ Nguyen & Huang (2002).
- ^ Bern & Eppstein (1993).
- ^ Ullman (1984); Burkis (1991).
- ^ Browning (1980). See especially Figure 1.1.5, page 15.
- ^ Hou et al. (2008); Wen et al. (2002).
- ^ Weisstein, Eric W. "Mandelbrot Tree". MathWorld（英語）.
参考文献
- Bern, Marshall; Eppstein, David (1993), “Worst-case bounds for subadditive geometric graphs”, Proc. 9th Annual Symposium on Computational Geometry, Association for Computing Machinery, pp. 183–188, doi:10.1145/160985.161018.
- Browning, Sally A. (1980), The Tree Machine: A Highly Concurrent Computing Environment, Ph.D. thesis, California Institute of Technology.
- Burkis, J. (1991), “Clock tree synthesis for high performance ASICs”, IEEE International Conference on ASIC, pp. 9.8.1–9.8.4, doi:10.1109/ASIC.1991.242921.
- Hou, Bo; Xie, Hang; Wen, Weijia; Sheng, Ping (2008), “Three-dimensional metallic fractals and their photonic crystal characteristics”, Physical Review B 77: 125113, doi:10.1103/PhysRevB.77.125113.
- Kaloshin, Vadim; Saprykina, Maria (2012), “An example of a nearly integrable Hamiltonian system with a trajectory dense in a set of maximal Hausdorff dimension”, Communications in Mathematical Physics 315 (3): 643–697, doi:10.1007/s00220-012-1532-x, MR 2981810.
- Leiserson, Charles E. (1980), “Area-efficient graph layouts”, 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pp. 270–281, doi:10.1109/SFCS.1980.13.
- Nguyen, Quang Vinh; Huang, Mao Lin (2002), “A space-optimized tree visualization”, IEEE Symposium on Information Visualization, pp. 85–92, doi:10.1109/INFVIS.2002.1173152.
- Ullman, Jeffrey D. (1984), Computational Aspects of VSLI, Computer Science Press.
- Wen, Weijia; Zhou, Lei; Li, Jensen; Ge, Weikun; Chan, C. T.; Sheng, Ping (2002), Subwavelength photonic band gaps from planar fractals, 89, Physical Review Letters, p. 223901, doi:10.1103/PhysRevLett.89.223901.
参考図書
- Kabai, S. (2002), Mathematical Graphics I: Lessons in Computer Graphics Using Mathematica, Püspökladány, Hungary: Uniconstant, p. 231.
- Lauwerier, H. (1991), Fractals: Endlessly Repeated Geometric Figures, Princeton, NJ: Princeton University Press, pp. 1–2.
外部リンク
- HTreeのページへのリンク
