B木が汎用的に使われない理由

Question

ハッシュ(辞書)を使うのは見たことがありますが、汎用データ構造としてB木を使用しているのを見たことがありません。

B木は走査も早いと思うのですがなぜ汎用的に使われないのでしょうか？

Answer 1

B-treeはデータベースやファイルシステムのインデックスで使用されています。データベースで頻繁に行われる範囲検索等について効率的な検索が可能なためです。

B-treeインデックス入門
SQLアタマアカデミー 第7回　性能改善の鍵，インデックスの特性を知る～B-treeとハッシュ　（1）B-tree

一方で単純な等値比較の性能ではハッシュに劣りアルゴリズも複雑なため、データベースのように柔軟な検索が必要とされるのでなければハッシュの方がよいでしょう。

Comments

[otaks]

ご回答ありがとうございます。
柔軟な検索とはどのようなものを指しますでしょうか？

[SVC34]

B-treeのデータは順序性を持っているため、以下のような検索を高速に行うことができます。

・範囲検索（特定の値より大きな値、小さな値の検索）
・前方一致検索（文字列等で先頭の一部のみ一致するデータの検索）
・最大値や最小値の検索
・整列済みの検索結果の取得（結果のソート処理が不要）