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 ベースのファイルシステムが数千ファイルで実質的に制限されていた問題を、ディレクトリごとに数千万ファイルを扱える程に改善した。
- ^ 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日閲覧。
[続きの解説]
「HTree」の続きの解説一覧
- 1 HTreeとは
- 2 HTreeの概要
H木
(HTree から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/30 05:39 UTC 版)
H木、H treeまたはH-Tree はフラクタル図形の1つであり、直線の両端に、その長さの1/√2の長さの垂線を追加し続けることによって構成される図形である。繰り返しパターンがアルファベットの "H" に似ているため、H木と呼ばれる。ハウスドルフ次元は2であり、矩形内の任意の点に対し、十分近いH木上の点が存在する。任意のステップにおいて、中心から端点までの距離がすべて等しい性質を利用し、VLSI設計とマイクロ波工学で用いられている。
- ^ 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（英語）.
[続きの解説]
- HTreeのページへのリンク
