B+Treeをざっくり理解したい この木なんの木
経緯
RDBのドキュメントを見るとよく出てくる木。
この木なんの木?
どんな木か知っておきたい。
木
バランス木のデータ構造の一つ。
バランス木についてはまた今度、掲載していきたい。
リーフノード同士が繋がっているため、範囲検索に適している。DBに適している訳だ。
リーフノードに行くとRowIDがあり、RowIDにデータの参照先がある。そのRowIDを頼りにデータにアクセスする。
検索が速いのはもちろん、アップデートや削除でもそこまで遅くないということからよく使われているとのこと。その辺りのメリット・デメリットはいつかまとめて見たい。
B-Treeとの違いはリーフノード同士が繋がっているかどうか。
木構造だから計算量も多くならないというのが利点O(logn)。
