多くのb +ツリーの例は整数キーを使用して実装されていますが、私は整数キーと文字列キーの両方を使っていくつかの例を見ていました。B +ツリーで文字列キーを実装する方法は?
答えて
文字列キーは、文字列へのポインタ(可能性が高い)です。
また、ほとんどの文字列に合わせてキーのサイズを変更することもできます。 64ビットは8バイトの文字列を保持し、16バイトのキーもそれほどばかげているわけではありません。
キーの選択は、実際にどのように使用するかによって異なります。
多段階のBツリーも使用します。文字列を持つと、testは[t、e、s、t]の配列として見ることができます。今、木の木について考えてみましょう。各ノードは特定の位置に対して1文字しか保持できません。また、配列や木などのリンクされたリンクリストのような特定のキー/値配列の実装について考える必要があります。また、ノードサイズを動的にすることもできます(文字数の制限)。
すべてのキーがリーフに合っている場合は、リーフにキーを格納します。リーフが大きくなると、新しいノードを追加できます。
それぞれのノードはその文字と位置を知っているので、リーフのキーからそれらの文字を取り除き、検索するか、リーフ+リーフの位置を知っていればそれらを再構成できます。
ツリーを作成した後、ツリーを特定の形式で書き込むと、1000文字の文字列で共有されていても各文字の組み合わせ(プレフィックス)を1回だけ格納する文字列圧縮が行われます。
単純な圧縮では、通常のテキスト(任意の言語で)と1:4のメモリで1:10の圧縮が行われることがよくあります。そしてまた、あなたはあなたがB +ツリーを使用し、あなたの辞書内の文字列である(任意の単語を検索することができます。
をこれは、あなたがマルチレベルを使用することができます1 EXTREMです。
データベースは、通常、特定のプレフィックスツリーを使用します(最初のx文字を残りの部分をリーフに格納し、リーフ内でバイナリ検索を使用します)また、実際の密度に基づいて可変長のプレフィックス長を使用する実装もありますので、最終的には非常に実装固有で、多くのオプション
ツリーが正確な文字列を見つけるのに役立つはずです。長さを追加したり、各文字の下位ビットのハッシュを使用したりすると、トリックがかかります。長さ(8bit)+ 4bit * 6文字= 32Bit - >あなたのハッシュコードからハッシュを食べました。または、最初の文字、最後の文字、および中間の文字を一緒に使用できます。長さは最も選択的なものの1つなので、あなたの文字列を検索しながら多くの衝突を見つけることはありません。
このソリューションは、特定の文字列を見つけるのに非常に適していますが、文字列の自然順序を破棄して、範囲クエリなどに応答する機会を与えません。しかし、あなたが特定のユーザー名/電子メールアドレスを検索したり、それらのツリーを検索している時には、それは後になります(ただし、質問はなぜハッシュマップを使用しないのですか)。
- 1. b +ツリーの完全実装
- 2. Mysql B +ツリーの実装
- 3. 既存のBツリーを実装する
- 4. Springの@ExceptionHandlerでカスタムエラー文字列を実装する方法は?
- 5. 文字列をJavaツリーに解析する方法は?
- 6. 変数名で文字列フォーマッタを実装する方法
- 7. CのオープンソースのBツリー実装はなんですか?
- 8. 単純な文字列検索を実装する方法
- 9. 文字列SCAudioStreamの実装方法は? - サウンドクラウド
- 10. Ocamlで文字列にツリー構造を高速に印刷する方法は?
- 11. RedBlackツリーでマルチセットを実装する方法は?
- 12. アンドロイドでツリー(タッチグラフ)を実装する方法は?
- 13. CでのB +ツリーの簡単な実装
- 14. B +ツリーとスナップショットアイソレーションによる遠隔照会の実装
- 15. 状態空間ツリーを実装する方法は?
- 16. 外部結合式ツリーを実装する方法は?
- 17. オプション[文字列]で文字列を設定する方法は?
- 18. は、キーの一部が文字列で
- 19. セグメンテーションフォールト - ベクトル文字列 - マルチマップの実装
- 20. 文字列のキーと値のペアのツリーのXSD
- 21. LINQで文字列の変換を実行する方法は?
- 22. ツリーへの文字列データ
- 23. 文字列をキーに変換する
- 24. 文字列配列の文字列長を取る方法は?
- 25. C++ 11 constexpr文字列の実装
- 26. Haskellのデフォルト文字列実装はなぜ文字のリンクリストですか?
- 27. Cで "文字列"のスタックを実装する
- 28. Python正規表現で文字列アンエスケープを実装する
- 29. IPadでツリー構造を実装する
- 30. Javaで汎用の `max(Comparable a、Comparable b)`関数を実装する方法は?
あなたの質問は非常に幅広く、文字列キーを使用してBツリーについてあなたが理解していないことは、特に明確ではありません。しかし、一般に、Bツリーは、対数の複雑さを持つ他の多くのツリーベースのデータ構造と同様に、キーを順序付けるために* comparison *を使用します。あなたのキーが整数の場合は、単純比較演算より小さいか大きい演算を使用できます。文字列の場合、通常は辞書編集による比較が行われます。例えば、 "AA" <"AB" 'Cでは、これは' strcmp'で行うことができます。 –