問題タブ [b-tree]

より良いインデックス構成を理解したい。2 つの列を持つテーブルがあるとします。

インデックスを作成したいと思います:

B-Tree インデックスの構成はどのようになりますか?

ageなどの 1 つの列の場合、組織は明確です。すべての非葉ノードには、検索に使用される一連の整数キーが含まれます。IDX_MultiColIdx B-Tree インデックスのノードを含む値はどれですか?

productなどのフィールドを持つ10M行のテーブルがありますcolor (int), price (float), weight (float), unitprice (int),...これで、Webのユーザーは、ランダムな条件（色はここで必須）と次のような順序でこのテーブルからデータをルックアップするクエリを動的に生成します

MySQLでこのように約10の可能なフィルタリングフィールド（範囲、並べ替えなど）を使用してテーブル（InnoDBまたはNDB）にインデックスを付ける方法は？

編集：私の理解では、MySQLはクエリに対して1つのインデックスのみを選択する可能性が高く、複合インデックスの左側の部分のみが機能します。(color, price, weight, create_date, unitprice, ....)明らかに、すべての可能な組み合わせにインデックスを付けることは、、 （color, weight, price, create_date, unitprice, ....)、 ...などの実行可能なオプションではあり(color, unitprice, weight, ....)ません。すべての条件が必ずしもすべてのクエリに存在するわけではありません。

このテーブルにインデックスを付けるにはどうしますか？

B-TreeデータベースはHashテーブルよりも高速であると聞いたので、プロジェクトにB-Treeデータベースを使用することを考えました。そのようなデータ構造を使用できるようにするPythonの既存のフレームワークはありますか、それとも最初からコーディングする必要がありますか？

本質的にハッシュベースのルックアップである現在のインデックス作成の実装よりも高速であるかどうかをテストしたいので、インデックス作成にツリー構造を使用して実験することを考えています。

Bツリー、AVLツリー、赤黒ツリーのパフォーマンスに関するさまざまな質問や記事を読んだことがありますが、パフォーマンスの面でそれらの違いはあまりわかりません。

人々が推奨するツリー構造とその理由は何ですか？理想的には、既存の.Net実装が利用可能である必要がありますが、必要に応じて独自の実装を行うことを嫌がりません。

私はB+Treeの一般的なC++実装を書き込もうとしています。私の問題は、B+ツリーに2種類のノードがあるという事実から来ています。子ノードへのキーとポインターを含む内部ノード、およびキーと値を含むリーフノード、および内部ノードのポインターは、他の内部ノードまたはリーフノードのいずれかを指すことができます。テンプレートを使用してこのような関係をモデル化する方法がわかりません（キャストや仮想クラスを使用したくありません）。

私の問題の解決策、またはC++でB+Treeを実装するためのより良い方法があることを願っています。

3〜4個の構成（3個の要素と4個のポインター）のノードを持つBツリーがあるとします。ルールに従って合法的にツリーを構築すると仮定すると、レイヤーに2つのノードがあり、1つのノードに4つの終了ポインターがあり、もう1つのノードに2つの終了ポインターしかない状況に到達することは可能ですか？

一般的に、適切に使用されたBツリーのバランスに関して私はどのような保証がありますか

私は整数の配列を持っていますが、それは数十万（またはそれ以上）に達する可能性があり、元々積み重ねられていた方法であるため、数値的に昇順で並べ替えられています。

配列をクエリして、>=入力された数値の最初の出現のインデックスをできるだけ効率的に取得できるようにする必要があります。考えもせずにこれを行う方法を知る唯一の方法は、条件がtrueになるまで配列テストを繰り返し、その時点で繰り返しを停止することです。ただし、これはこの問題に対する最も費用のかかる解決策であり、私はそれを解決するための最良のアルゴリズムを探しています。

私はObjective-Cでコーディングしていますが、応答できる人々の聴衆を広げるためにJavaScriptで例を示します。

この検索を実行するためにこのデータをDBに入れることは、メモリ内でこれにすばやく取り組むためのある種のアルゴリズムを見たいと思っているので、最後の手段にすぎません。

私のプログラムはすでに各番号をこのスタックに1つずつプッシュしているので、データ構造を変更したり、配列を構築するときに追加のデータ構造を保存したりすることができます。そのため、次のコードを変更するだけです。それらをスタックに追加します。スタックに追加されているインデックスを検索することはできません。これは、検索操作が事後に異なる値で頻繁に繰り返されるためです。

今は「B-Tree」を考えていますが、正直なところ、どうやって実装すればいいのかわからないので、それを理解する前に、この単一のユースケースに合う素晴らしいアルゴリズムがあるのではないかと思います。より良い？

データベースに関するbtree定理に関する記事をたくさん読んでいます..常に当惑することがあります。
次のように説明されているテーブルがあると仮定します:
table userinfo:
(主キーとしての user_id、文字列としてのユーザー名、文字列としてのパスワード)
いくつかの記事で説明されているように、user_id はテーブルuserinfoのインデックスとして作成され、効率的なパフォーマンスが得られます。 user_idのインデックスでレコードを選択した場合..しかし、usernameで選択した場合、行を 1 つずつカンパリングすると言われます..... MYSQLでこれを試してみましたが、予想ほど遅くはありません.... なぜですか? mysqlはこの選択を どのように処理しますか?? ありがとう

これは宿題からです：

各ページ (ディスク ブロック) が 16K バイトで、各 KVP が 8 バイトであるとします。したがって、最小サイズ (16000/8)/2 = 1000 の B ツリーを使用することにします。T をそのような B ツリーとし、T の高さを 3 と仮定します。 Tに保存されますか？あなたの答えを簡単に説明してください。

B ツリーのプロパティにより、次の点に注意してください。
各ノードには最大 2000 個のキーがあります。
各ノードには少なくとも 1000 個のキーがあります (ルート ノードを除く)。

メモリがどのようにキーの数を制限しているのか理解できません。各ページには 16000 バイトのスペースがあり、各キーは 8 バイトを占めるため、各ページには 2000 個のキーを格納できます。これは、とにかく各レベルで格納できるキーの最大数です。

以下は私の計算です:
キーの最小数 = 1000(1001)(2) + 1 = 最小で 2002001 キー
(ルートは少なくとも 1000 キーを持つように制限されていないため) キー
の最大数 = 2000(2001)(2001 ) = 最大 8008002000 キー

質問がこれほど単純ではないため、何か重要なものが欠けていると感じています。

BerkeleyDB を使用しているときにアクセス方法の選択を促進するものを理解しようとしています: B-Tree と HashTable。Hashtable は O(1) ルックアップを提供しますが、挿入は高価です (Linear/Extensible ハッシュを使用すると、挿入のために償却された O(1) が得られます)。しかし、B ツリーはログ N (ベース B) のルックアップと挿入時間を提供します。B-Tree は、範囲クエリをサポートし、並べ替えられた順序でアクセスすることもできます。

1. これらの考慮事項とは別に、他に何を考慮する必要がありますか?
2. 範囲クエリをサポートする必要がない場合、Hashtable アクセス メソッドを使用できますか?