B-tree
AVL木は、二分木の話だったが、多分木に一般化する
つまり、多分木でかつ、回転させることで平衡木構造を保つ insertのformに1個ずつ適当な値をinsertしていける
1ノードから最大$ m個の枝が出る時、オーダー$ mのB-treeと言う
$ \frac{\log_2{n}}{\log_2{m}}
$ mを増やすことで処時間を短縮できる
増やしまくったら結局1階層になって意味ないと思うけど、南下条件があるの？
図
https://gyazo.com/59e3bb0b0c5508f1a8e92f88e495f3d2
3種類のノード
ルートノード
子ノード
リーフノード
↑この3種類であることは固定
ただ、それぞれのノードの個数は変わりうる
例えば、これで、Max Degree 4にすれば、 子ノードが3つになる
上の図は、子ノードが2つずつ、リーフノードも2つずつになっている
キーとか値とか言っているのがイマイチわかっていない
値そのままキーとして扱うとなにか困ることがあるのか？
関連