Bツリーキーの値はどこに保存されていますか？

Question

私は自分の鍵となると思う一意のIDを持つ各文字列を10k文字列のデータベースに格納するためのB-Treeを研究しています。しかし、私が見たすべての実装は、値ではなくBツリーのキーだけを表示します。私はB-Treeがマップとして機能するときに値をキーにリンクしなければならないと確信していますが、ツリーのノード内にキーとともに格納されているかどうかはわかりません。例えば。

 ||key3| |key6|| 
    /  |   \ 
    / ||key4| |key5|| \ 
/      \ 
||key1| |key2||   ||key7| |key8|| 

---

 ||k3,v3| |k6,v6|| 
    /  |   \ 
    / ||k4,v4||k5,v5|| \ 
/      \ 
||k1,v1| |k2,v2||   ||k7,v7| |k8,v8|| 

私がどこでどのように値が格納されていることを確認していません。

Answer 1

すべての単一ノードでは、内部およびリーフの両方にキーがあります。

B +ツリーでは、すべてのキーがリーフノードで使用できます。だから、葉ノードを分割する場合は、親にキーを押してもらうだけで、自分の値を保持することができます。しかし、Bツリーではキーが繰り返されないので、内部ノードに値を持たなければなりません。

キー値マップを使用して、ツリー固有の機能のキーを反復することができます。キーを並べ替える必要があるので、JavaのTreeMapやC++の単純なstd :: mapなどのソートされたマップを使用する必要があります。 （Pythonには標準ライブラリのようなものはありません）。ノードを簡単に分割し、新しいノードに物事をプッシュするのにも役立ちます。