c - B+ ツリーで文字列キーを実装する方法は?

Question

多くの b+ ツリーの例は整数キーを使用して実装されていますが、整数キーと文字列キーの両方を使用する他の例を見たことがあります。b+ ツリーの基礎を学びましたが、文字列キーの仕組みがわかりません。

Answer 1

マルチレベルの B-Tree も使用します。文字列があると、test は [t,e,s,t] の配列と見なすことができます。ここで、木からなる木について考えてみましょう。各ノードは、特定の位置に 1 文字しか保持できません。また、配列の連結リストやツリーなど、特定のキー/値配列の実装についても考える必要があります。また、ノード サイズを動的にすることもできます (文字数の制限)。

すべてのキーがリーフに収まる場合は、リーフに格納します。葉が大きくなったら、新しいノードを追加できます。

そして、各ノードはその文字と位置を知っているので、葉のキーからそれらの文字を取り除き、検索するとき、または葉 + 葉の位置を知っている場合はそれらを再構築できます。

ツリーを作成した後、ツリーを特定の形式で記述すると、1000 エンドの文字列で共有されている場合でも、各文字の組み合わせ (接頭辞) を 1 回だけ格納する文字列圧縮が行われます。

単純な圧縮では、多くの場合、通常のテキスト (どの言語でも!) は 1:10 に圧縮され、メモリでは 1:4 に圧縮されます。また、任意の単語 (B+Tree を使用した辞書内の文字列) を検索することもできます。

これは、マルチレベルを使用できる極値の 1 つです。

データベースは通常、特定のプレフィックス ツリーを使用します (最初の x 文字と残りをリーフに格納し、リーフ内で二分探索を使用します)。また、実際の密度に基づいて可変プレフィックス長を使用する実装もあります。したがって、最終的には非常に実装固有であり、多くのオプションが存在します。

ツリーが正確な文字列を見つけるのに役立つかどうか。多くの場合、長さを追加し、各文字の下位ビットのハッシュを使用するとうまくいきます。たとえば、長さ (8 ビット) + 4 ビット * 6 文字 = 32 ビット -> ハッシュ コードからハッシュを生成できます。または、最初、最後、および中間の文字を一緒に使用することもできます。長さは最も選択的なものの 1 つであるため、文字列の検索中に多くの衝突を見つけることはありません。

このソリューションは、特定の文字列を見つけるのに非常に適していますが、文字列の自然な順序を破壊するため、範囲クエリなどに答える機会がありません. しかし、特定のユーザー名/電子メールまたはアドレスを検索する場合は、それらのツリーの方が優れています (ただし、問題は、ハッシュマップを使用しない理由です)。

Answer 2

文字列キーは、文字列へのポインタにすることができます (ほとんどの場合)。

または、ほとんどの文字列に合うようにキーのサイズを変更することもできます。64 ビットは 8 バイトの文字列を保持し、16 バイトのキーでさえばかげているわけではありません。

キーの選択は、それをどのように使用するかによって大きく異なります。