【データベース基礎】B+Treeインデックスまとめ

  • 8
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

目次

■B+Treeインデックス
■B+TreeとB-Tree構造
■B+Treeの柔軟性
■まとめ
■参考文献

B+Treeインデックス

B+Treeインデックスは、木構造になったインデックスです。
以下、イメージ図
image
(出典:なぜBTreeがIndexに使われているのか)
頂上を「ルートブロック」,最下層を「リーフブロック」,その間を「ブランチブロック」といいます。
ルートブロック,ブランチブロックは、検索のキーになるIDに対してそれぞれ対象ブロックがどこにあるのかというデータを所持しています。
そして、最下層のリーフブロックが実際の格納位置の情報を持っています
データを取得する場合、ルート→ブランチ→...→リーフという順序でデータ取得をします。

ハッシュ構造で、データを保持するハッシュインデックス(【データベース】高速アクセスのためのインデックス基礎まとめ)と比べると、
格納位置までの手数が増えてしまいますが、十分に効率の良いインデックス構造です。

B+TreeとB-Tree構造

B+Tree構造 => 末端のリーフブロックのみで格納位置を管理
B-Tree構造 => すべての値をリーフブロックで管理しているとは限らない

B+TreeとB-Tree構造のメリット・デメリット
スクリーンショット 2016-07-30 20.51.20.png
(筆者作成)
以上からもわかるように、リーフブロックで値を一括管理しているB+Tree構造では、広範囲検索で非常にメリットを発揮します。
そのため、RDBMSでは、B+Tree構造が広く使われています。

B+Treeの柔軟性

B+Tree構造のメリットで記述したことと被りますが、
B+Tree構造では、イコール検索はもちろん,不等号検索や、前方一致検索といった
事前に返ってくる値が明確ではない広範囲な検索が可能です。
この場合、その都度ブランチを辿ることなく完結する(リーフブロックの参照のみ)ので、その分高速になります

まとめ

  • B+Tree構造は、木構造になっている
  • B+Tree構造の最大のメリットは、リーフブロックで値を一括管理していること
  • B+Tree構造は、広範囲のデータ取得の高速化を実現できる

参考文献

B-treeインデックス入門
なぜBTreeがIndexに使われているのか
Bツリー・インデックスの構造
Webエンジニアのための データベース技術[実践]入門 (Software Design plus)
松信 嘉範