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

Question

多くのb +ツリーの例は整数キーを使用して実装されていますが、私は整数キーと文字列キーの両方を使っていくつかの例を見ていました。

Answer 1

文字列キーは、文字列へのポインタ（可能性が高い）です。

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

キーの選択は、実際にどのように使用するかによって異なります。

Answer 2

多段階のBツリーも使用します。文字列を持つと、testは[t、e、s、t]の配列として見ることができます。今、木の木について考えてみましょう。各ノードは特定の位置に対して1文字しか保持できません。また、配列や木などのリンクされたリンクリストのような特定のキー/値配列の実装について考える必要があります。また、ノードサイズを動的にすることもできます（文字数の制限）。

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

それぞれのノードはその文字と位置を知っているので、リーフのキーからそれらの文字を取り除き、検索するか、リーフ+リーフの位置を知っていればそれらを再構成できます。

ツリーを作成した後、ツリーを特定の形式で書き込むと、1000文字の文字列で共有されていても各文字の組み合わせ（プレフィックス）を1回だけ格納する文字列圧縮が行われます。

単純な圧縮では、通常のテキスト（任意の言語で）と1：4のメモリで1：10の圧縮が行われることがよくあります。そしてまた、あなたはあなたがB +ツリーを使用し、あなたの辞書内の文字列である（任意の単語を検索することができます。

をこれは、あなたがマルチレベルを使用することができます1 EXTREMです。

データベースは、通常、特定のプレフィックスツリーを使用します（最初のx文字を残りの部分をリーフに格納し、リーフ内でバイナリ検索を使用します）また、実際の密度に基づいて可変長のプレフィックス長を使用する実装もありますので、最終的には非常に実装固有で、多くのオプション

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

このソリューションは、特定の文字列を見つけるのに非常に適していますが、文字列の自然順序を破棄して、範囲クエリなどに応答する機会を与えません。しかし、あなたが特定のユーザー名/電子メールアドレスを検索したり、それらのツリーを検索している時には、それは後になります（ただし、質問はなぜハッシュマップを使用しないのですか）。