2010年10月2日 (土) 05:32時点における版編集 F-mikanBot (会話 \| 投稿記録) 10,576 回編集 m ロボットによる: 良質な記事へのリンク de:B-Baum ← 古い編集		2010年11月22日 (月) 12:58時点における版編集取り消し Penn Station (会話 \| 投稿記録) 編集フィルター編集者、ビューロクラット、チェックユーザー、インターフェース管理者、オーバーサイト、管理者 70,870 回編集 m link fix 新しい編集 →
1行目: '''B木'''（びーき、~~''B~~[[英語]]：B-~~tree''）~~tree）は、[[コンピュータサイエンス]]における[[データ構造]]、特に[[木構造 (データ構造)\|木構造]]の一つ。ブロック単位のランダムアクセスが可能な[[補助記憶装置]]（[[ハードディスクドライブ]]など）上に木構造を実装するのに適した構造として知られる。実システムでも多用されており、[[データベースマネージメントシステム]]の多くはB木による索引を実装している（B木の改良型または亜種である[[B+木]]や[[B木]]を使うことが多い）。 == 構造 == [[~~ファイル~~File:B-tree example.svg\|thumb\|right\|380px\|B木の例~~\|thumb\|384px\|right~~]] 多分木の平衡木(バランス木)である。1 ノードから最大 ''m'' 個の枝が出るとき、これをオーダー ''m'' のB木という。後述する手順に従って操作すると、根と葉を除く「内部ノード」は最低でも ''m'' /2 の枝を持つことを保証できる。各ノードは、枝の数 - 1 のキーを持つ。枝<sub>1</sub> ～枝<sub>''m''</sub> とキー<sub>1</sub> ～キー<sub>''m'' -1</sub> を持つとき、枝<sub>''i''</sub> にはキー<sub>''i'' -1</sub> より大きくキー<sub>''i''</sub> より小さいキーだけを保持する（キーの重複を許す場合はどちらかに等号をつける）。葉ノードの定義は文献によって違いが見られる。木の終端を[[~~ヌル (コンピュータ)~~Null\|ヌルNullポインタ]]のような特殊な値で表す場合、枝がすべて終端記号となっているノードを葉とする。これに対して一部の文献では、終端を表すためにキーが0個のノードを連結し、このノードを葉と定義している。すなわち、後者の定義における葉ノードの親が、前者の定義における葉ノードとなる。後者の定義をとる文献では「葉ノードはキーを持たない」ということになる。以下の記述では、前者の定義に従うものとする。ノードはページと呼ばれることもある。特にハードディスクドライブなどの外部記憶装置を使ってB木を実現する場合によく見られる。この場合、各ノード（ページ）のサイズが、外部記憶装置のブロックサイズの整数倍になるようにオーダーを調整することが多い。 28 ⟶ 27行目: === 挿入 === [[~~ファイル~~File:B-tree-splitt.png\|thumb\|right\|380px\|B木におけるノードの分割~~\|thumb\|396px\|right~~]] <!--[[画像File:B-tree example split.svg\|thumb\|right\|250px\|B木におけるノードの分割~~\|thumb\|256px\|right~~]]--> 検索の処理を行うことで、挿入しようとする値が木のどこに位置するべきかがわかる。まだ登録されていない値を検索した場合、処理は必ず葉ノードまで達することに注意。すなわち、挿入処理は常に葉ノードを対象として開始される。ノードにまだ新たなキーを登録する余地がある場合、キーを追加して挿入処理は終了する。 50 ⟶ 49行目: == 外部リンク == {{Commonscat\|B-Trees}}▼ [http://www.cl.cam.ac.uk/~smh22/docs/ubiquitous_btree.pdf Ｂトリーの普遍性について（英語）] ▲{{Commonscat\|B-Trees}} {{DEFAULTSORT:Bき}} [[Category:データ構造]] [[Category:データベース]] {{Link GA\|de}} [[ca:Arbre-B]] [[cs:B-strom]]

「B木」の版間の差分