応用情報技術者 予想問題｜練習問題 第29問

解説

B+木は多分木のバランス木で、内部ノードには探索用のキーのみを置き、実データ（または行へのポインタ）をすべて葉ノードに格納し、葉同士をキー順にポインタで連結する構造を持つ。1ノードに多数のキーを収めるため木の高さが低く抑えられ、ディスクI/O回数が少なくて済む。等値検索・挿入・削除はO(log n)で行え、さらに葉の連結リストをたどるだけでBETWEENのような範囲検索を効率的に処理できる点がRDBMSのインデックスに採用される主な理由である。データを完全にメモリ上に保持する必要があるという記述は誤りで、むしろディスク格納を前提とした構造である。常にO(1)で検索できるのはハッシュインデックスの特徴だが、範囲検索には対応できない。NULL限定という性質もない。「範囲に強いB+木、等値専門のハッシュ」と対比で覚える。