java - BTree の容量を理解する

Question

BTrees について私が理解したことは次のとおりです。

• ルート BTree のサイズが 32 の場合、レベル 1 には 1024 個のキー容量があります
• レベル 2 は 1048576 個のキーを並べ替えることができます
• リーフが半分埋まっているため、実際の容量はレベル 1 で 512、レベル 2 で 524288 です。

私は大丈夫ですか、それとも明らかに心配していませんか?

Answer 1

Btree の容量を計算する式: 子の最大数が D であると仮定すると、任意のノードのキーの最大数は D-1 です。レベル 1 (ルート レベル) には、常に D-1 キーを持つノードが 1 つあります。レベル 2 は最大で D ノードを持つことができ、各ノードは最大で D-1 キーを持つことができるため、レベル 2 には D*(D-1) キーがあります。レベル 3 は最大で D^2 個の子を持つことができます (レベル 2 のノードは D 個の子を持つことができ、レベル 2 には最大で D 個のノードがあるため)。レベル 3 のこれらのノードのそれぞれは、最大で D-1 個のキーを持つことができます。したがって、レベル 3 のキーの数は D^2 * (D-1) であり、以下同様です ...任意のレベル i について、最大数キーは D^(i-1) *(D-1) です。したがって、ツリーの容量は、各レベルの容量を合計することによって得られます。