問題タブ [b-tree]

mysql および/または postgres には、btree のリーフに小さな btree がありますか? 複数の列でインデックスを使用しているとしたら、それは便利な機能です。

それとも、インデックスのキーは区切り記号だけで区切られたものですか?

質問に関連する投稿を読んで解決策を考え出すために数時間を費やしましたが、解決策を見つけるのに実際には成功しませんでした。

だからここに行く：私はかつてインタビューで、特定の単語がファイルに存在するかどうかを検索するためにどのデータ構造を使用するかを尋ねられました。また、ファイルはメモリに収まらないほど大きいと思われ、インタビュアーは実際にディスク上のソリューションを探していました。

Bツリーはディスク上のデータ構造ですか？

二分探索木はメモリ内のデータ構造ですよね？

大量のトランザクションが発生しているので、現在のデータベースでロックがどのように実装されているかについての情報を取得したいと思います。ゼロバジェットで作業している私の選択は、mysql5.5とpostgres9.0に制限されています。

ロックを比較するサイトはありますか？

文献から、読み取り専用ロックと読み取り/書き込みロックを設定できること、およびロックを処理する良い方法はデータへのパスをブロックすることであることを知っています。これは、btreeの一部をブロックすることを意味します。しかし、これらのデータベースがどのように機能するかについての詳細はわかりません。

どうもありがとう。

私は b ツリーについて学ぼうとしていますが、見つけることができるすべてのソースでは、b ツリーのプロパティを保持しながらツリーから要素を削除する方法についての議論が省略されているようです。

誰かがアルゴリズムを説明したり、それがどのように行われたかを説明するリソースを教えてくれますか?

実装が比較的簡単で、スケーリング（複数ノード）に適している同時実行技術に興味があります。

また、より高度なアルゴリズムを知っている場合は、情報を提供してください。

このトピックが他の人に役立つことを願っています。ありがとう！

アップデート

私は nosql ストレージとモデルに興味があります。

私はPostgreSQLが初めてです。構築する必要があるハイブリッド データベースについて、非常に珍しい要件があります。私が見たモジュールから、次のことが可能であるように思えます。

テーブルに実際にデータを追加せずに、キー - [値] をインデックスに追加できるようにする必要があります。簡単に言えば、理想的には btree (ルックアップ速度) として、キー [値] ストアが必要です。インデックス構造が理想的です。おそらく、別の構造がこれを行うでしょう。

具体的には、次のようなものを保存したいと思います。

このデータを保存してインデックスを作成するオーバーヘッドは必要ありません。いわば「インデックス付けされているが保存されていない」データが必要なだけです。

同様に重要なのは、これらの構造を照会してデータ (ID) を取得し、ID に対して INTERSECTS などを実行したり、キーに対して IN、BETWEEN、= などを実行したりできることです。

お察しのとおり、最終的な目標は ID の最終的なリストであり、それがクライアントに送信され、必要に応じて検索されます。

編集

私がしたくないのは、すべての値のキーを記録することです。上記の例を使用すると、{Blue, 10}、{Blue, 20} などは保存したくありません。{Blue, [10, 20, 23, 47]} を保存したいのです。

これを従来のテーブルとして保存すると、この重複の問題を回避する方法がわかりません。

青 [10, 20, 23, 47]} をもう一度見てみると、これは技術的には、ID (10, 20, 23, 47) が値としてマークされ、親キーが「青」である単一の btree にすぎません。キーとしてマークされています。

このデータ型の不一致は単一のツリーでは厄介になる可能性があるため、理想的な解決策は「[btrees] in a btree」であると思います。ここで、「btree」がキーで、[btrees] は a の値の各グループの btree です鍵。

SQL Server がクラスター化インデックスのリーフ レベルで行のデータを格納できることを知っています。PostgreSQL はこれを行わないと思います。もしそうなら、そのストレージパラダイムは何ですか?

私の主な質問は次のとおりです。次の設計とデータを検討してください (T-SQL に示されています)。

これは両方の列を PK とする btree であるため、「[Key] = 1」は 1 回だけ格納され、「ID = [1, 2, 3, 4]」は個々の値になるというのは正しいでしょうか。 PK の一部ではない行列がないため、sé ごとに葉の値はありませんが、btree ですか?

これは PostgreSQL でどのように機能しますか?

この B ツリーに 3 つの値、60、61、および 62 を挿入しようとしています。ノードがいっぱいで、親が空の場合に値を挿入する方法は理解していますが、親がいっぱいの場合はどうでしょうか。

たとえば、60 と 61 を挿入すると、そのノードがいっぱいになります。親、または親の親を拡張できません (いっぱいであるため)。親の値を変更できますか？挿入前と挿入後の B ツリーのイメージを提供しました。

60、61、62 を挿入しようとしました: ルートの 66 を 62 に変更し、62 を <72 ノードに追加したことに注意してください。これはこれを行う正しい方法ですか？

Java用の軽量で高速で、できれば安定したBツリー（または同様の）ライブラリを推奨できる人はいますか?

基本的に、ディスク上のマップを探しています。BerkeleyDB JE の方針に沿ったものですが、トランザクションは必要なく、読み取り専用の同時実行で問題なく、サイズが約 1/10 である必要があります (BSD または Apache ライセンスも必要です)。

純粋な Java である必要があるため、東京/京都のキャビネットはありません。

関連するインターフェイスを実装するCollectionsことはプラスになります (代わりに、プリミティブ型のテンプレート化されたインターフェイスも良いでしょう)。

JDBMはかなり良さそうに見えますが、2005 年に (1.0 で) 放棄されたようです。

DiskBackedMapもありますが、彼らは 1 年前にアルファ版をリリースし、それ以降何もリリースしていません。

他に何かありますか？または、上記のものの経験はありますか？

私が探していないもの：

• インプロセス リレーショナル DB (H2、Derby、SQLite などはありません)
• 分散キー値ストア (Redis、Memcachedb、Cassandra、Voldemort、Dumbledore などはありません)

誰でもこのセグメンテーション違反を取り除くのを手伝ってくれますか? 私はこのコードに 1 週​​間取り組んでいますが、まだこれをデバッグできません。このコードは Btree の実装です。挿入部分は正常に動作していますが、削除にセグメンテーション違反があります。デバッグできません。誰か助けてください。

このリンクに基づいて入力を行いました（アルファベット値をASCII値に変換しました） http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

最初のH(同等の ASCII 値) を削除すると正常に動作しますが、T(同等の ASCII 値) を削除するとセグメンテーション違反が発生します。

何が問題なのですか？