theory - btree と b+tree はデータをリーフにのみ保存しますか?

Question

b ツリーと b+ ツリーはデータをリーフにのみ保存しますか? 内部ノードを使用して必要なデータを検索すると想定しています。

そうですか、それともすべてのノードにデータを保存しますか?

Answer 1

非リーフ ノードの「レコード」には次が含まれます

• ツリーの下の次のレベルにあるノードへのポインタ (一種のノード「アドレス」)
• そのノードの最初の (または実装に応じて最後の) レコードのキーの値

このような非葉の「レコード」は、キーの順序でリストされているため、非葉ノードをスキャン (または内部でバイナリ検索) することで、次のレベルのどのノードが検索された値を含む可能性があるかがわかります。

リーフ ノード レコードには、完全なデータ レコード (キー値など) が含まれます。

したがって、「実際の」データはリーフ ノードにのみ含まれ、非リーフ ノードにはキー値 [のコピー] のみが含まれます。データのごく一部 (この割合は、リーフ ノードで見つかったデータ レコードの平均数に依存します)。

これは、B+ ツリーに関するウィキペディアの記事の次の図に示されています。

一番上の非リーフ ノード (この単純なツリーで唯一のノード) には、2 つの非リーフ ノード レコードのみが含まれ、それぞれにキー値のコピー (青みがかった色) と対応するノードへのポインター (灰色) があります。 ）。このツリーにはたまたま 2 つのレベルしかないため、ルート ノードの「レコード」はリーフ ノードを指します。追加のレベルがあることが想像できます (以下に示す一番上のツリーの上に、「3-5 ノード」と呼びます)。その場合、上記のノードには (他の同様のレコードと共に)、「3-5」ノードへのポインターを持つキー値 3 のレコードが含まれます。
また、キー値 3 と 5 のみが非リーフ ノードに含まれていることに注意してください (つまり、すべてのキー値が非リーフ ノードで再現されるわけではありません)。
次のノードの最後のレコード (代わりに最初のレコードが使用された場合にも機能しますが、検索ロジックが実装される方法がわずかに異なります)。

リーフ ノードには、キー値 (青みがかった色) と対応するデータ レコード (d1、d2... は灰色で表示) が含まれます。各リーフ ノードの最後に表示される赤みを帯びたポインターは、次のリーフ ノードを指します。つまり、キー順で次のデータ レコードを含むノードです。これらのポインターは、データ レコードの範囲を「スキャン」するのに役立ちます。

Answer 2

すべてのデータはリーフにあります。

B+ のウィキ。