1

私はc++で二分木を使い始めましたが、後でデータのチャンクをすぐに読み取れる順序でデータをディスクに保存することを考えるまで、私はそのアイデアが本当に好きで、物事は明確であると言わなければなりません。これまでのところ、すべて（ノード）をRAMに保存しました...しかし、これは単純で実際のアプリではありません。バイナリツリー全体をディスクに保存することには興味がありません。メモリに再度読み取る必要があるため、再び役に立たないからです。私が求めているのは、たとえばMYSQLのようなメソッドです。これに関する良い記事は見つかりませんでしたので、誰かがURLや本を含めていただければ幸いです。

4

1 に答える 1

2

b-treeおよびb+treeとの主な違い：-リーフノードは、高速ロックアップシーケンシャル読み取りのためにリンクされています。昇順、降順、またはその両方を指すことができます（1つのIBM DBで見たように）

  • ディスクに書き込む必要があります。テーブルまたはファイルが大きくなると、メモリの問題が発生します。（ファイルに対するSEEK操作は非常に高速です。1秒未満でディスク上に1 GBのファイルを作成できます。..C＃filestream、method .SetFilesize）

  • 複数のリーダー/ライターを管理している場合は、インデックスとテーブル（またはファイル）の同時実行制御が必要です。メモリ内でそれを実行しますか？停電が発生した場合、どのようにロールバックしますか？

IE：フィールドf1にインデックスが付けられます。

WHERE 1 = 1（b + treeにアクセスする必要はありません、すべてを教えてください。順序は関係ありません）

WHERE 1 = 1 ORDER BY f1 ASC / DESC（b + treeにアクセスする必要があり、すべて昇順/降順で指定してください）

WHERE f1> = 100（b + treeにアクセスし、リーフノード= 100の場所をロックして、すべてのリーフノードアイテムを正しいポインタの後に指定する必要があります。このプロセスがマルチスレッド読み取りの場合、おそらく奇妙な順序になりますが、問題はありません。 ... in句による順序なし）。

WHERE f1> = 100 order by f1 asc（b +ツリーにアクセスする必要があります。リーフノード=100の場所をロックし、すべてのリーフノードアイテムを正しいポインタの後に指定します。このプロセスは、b+ツリーの後にマルチスレッド化しないでください。自然に順番に実行されます。 。

b+treeとタイプ文字列でインデックス付けされたフィールドf2。

'％ODD'のような名前（内部的には、比較された値を反転し、すべての記号を最後に残す必要があります。Likeは' DDO'で始まり、何かで終わります。'DDOT'はグループ内にあるため、'TODD'は結果!!!!トリッキーでトリッキーなロジック;P）

このステートメントでは、WHERE名は「％OD％」のようになります（中央に「OD」があります）。物事は熱くなります:)）））内部的には、結果は「OD％」のサブ結果のUNIONであり、サブ結果は「DO％」と反転しています。その後、「OD」の開始と「OD」の終了を削除します。それ以外の場合は、有効な結果です（「ODODODODOD」は有効な結果です。無効な結果は「ODABCD」と「ABCDOD」）。

私が言ったことを検討し、あなたが深くやるなら、さらにいくつかのことをチェックしてください：-ファイルのFastIO：C＃ファイルストリームno_buffered_flag、wriththoughtディスクフラグ。-メモリマップファイル/メモリビュー：はい、必要に応じて巨大なファイルを少しずつ操作できます-インデックス：ビットマップインデックス、ハッシュインデックス（ハッシュ関数;完全なハッシュ関数;ハッシュ関数のあいまいさ）、スパースインデックス、デンスインデックス、 b + tree、r-tree、逆インデックス。-マルチスレッド：ロック、ミューテックス、セマフォ-トランザクションの考慮事項（ログファイル、2フェーズコミット; 3フェーズコミット）; -ロック（データベース、テーブル、ページ、レコード）-デッドロック：それを強制終了する3つの方法（より長い競合プロセス;より若い競合プロセス;より多くのオブジェクトをロックするプロセス）。最新のRDBMは、3つの方法を組み合わせて使用​​します...-SQL解析（ASTツリー）。-繰り返し発生するクエリのキャッシュ。-トリガー、手順、ビューなど。

  • すべてをメモリにロードしないでください。インテリジェントなソリューションは、必要に応じてパーツをロードし、使用できなくなったときにリリースします。なぜ=>データベースエンジン（およびPC）は、より少ないメモリを使用してより応答性が高くなります。ブランチリーフノードをロックアップするためにb+treeを使用すると、必要なディスクIOは2つだけです。ロックアップ値がわかれば、レコードの長いポインターが得られます。ポジションのメインファイルを探し、内容を読みます。これは速すぎます。メモリは高速です...はい、そうですが、10GBのb+ツリーをメモリに配置できますか？もしそうなら、あなたのDBエンジンプログラムはどのように動作し始めますか？だらしない？

二分木と従来のbtreeを忘れてください：それらは学術的なチュートリアルです。実際には、ハッシュテーブルまたはb +ツリーに置き換えられます（B PLUS TREEはストレージを示し、昇順で並べ替えられます-http ://en.wikipedia.org/wiki/B%2B_tree）

  • 複数のディスクのdbデータにデータスペースを使用することを検討してください。ディスクIOのパフォーマンスを並列化できます。それらをミラーリングすることを忘れないでください...各データスペースには、部分的なログファイルを含むインデックスのフラグメントを含むテーブルのフラグメントが必要です。サブユニットのクエリを賢く提示するコーディネーターを開発する必要があります。

IE：3つのデータスペース...INSERTINTOなど......1つのテーブルスペースでのみ発生する必要があります。

ただし、TB_XPTOから*を選択すると、すべてのデータスペースに表示されます。

select * from TB_XPTOインデックス付きフィールドによる順序で、すべてのデータスペースに表示する必要があります。各データスペースが命令を実行するため、サブオーダーごとに3つのサブセットがあります。

結果はコーディネーターに送られ、そこで再度注文されます。混乱しますが、速いです!!!!!!

コーディネーターはマスタートランザクションを制御する必要があります。

データスペースAがコミットされたデータスペースBがコミットされたデータスペースCがコミットされていない状態の場合、コーディネーターはC、B、およびAをロールバックします。

データスペースAがコミットされたデータスペースBがコミットされたデータスペースCがコミットされた場合、コーディネーターはトランザクション全体をコミットします。

コーディネーターログ：CREATE MASTER TRANSACTION UID 121212、CHILD TRANSACTIONS（1111,2222,3333）

データスペースログ1111INSERTlenバイト配列1111INSERTlenバイト配列COMMIT1111

データスペースBログ2222INSERTlenバイト配列2222INSERTlenバイト配列COMMIT2222

DATA SPACE C LOG 3333 INSERT len byte array3333--->もう何もありません.....ここで電源障害が発生しました!!!!!!!

起動コーディネーターで、データベースが適切に閉じられているかどうかを確認します。閉じられていない場合は、ログファイルを確認します。さて、COMMIT 121212のようなマスターコミット行がありません。したがって、ログの整合性についてデータスペースに問い合わせます。A、BはCOMMITEDを応答しますが、Cはログファイルを確認した後、障害を検出します。UNCOMMITEDに返信します。マスターコーディネーターは、ロールバックのためにテーブルスペースA、B、Cを強制します1111,2222,3333その後、自分自身がマスタートランザクションをロールバックし、DB状態=OKにします。

ここでの主なポイントは、挿入、選択、更新、および削除の速度です。

  • インデックスのバランスを保つことを検討してください。インデックスを削除すると、バランスが崩れます。不均衡なインデックスはそのパフォーマンスを低下させます...それを制御するために、インデックスファイルの先頭にヒープを追加します。ここでいくつかの数学が役立つでしょう。削除がレコードの5％を超える場合は、バランスを取り、カウンターをリセットします。インデックス付きフィールドの更新が終了した場合は、それもカウントする必要があります。

  • フィールドインデックスを考慮して賢くしてください。列が性別の場合、オプションは2つしかありません（私は願っています、笑.... ops、null許容も可能です....）、ビットマップインデックスが適切に適用されます。Oracleのようなフィールドに適用されるシーケンスやSQLServerのようなIDフィールドのように、フィールドの区別（私はそれをひどく綴っていると思います）が100％（すべての値が異種）である場合、b+treeは適切に適用されます。Oracleのように、フィールドが一種の幾何学的タイプである場合は、Rツリーが最適です。文字列の場合、逆インデックスが適切に適用されます。異種の場合はb+treeが適用されます。

  • ヒューストン、問題があります.... NULL値フィールドは、インデックスでも考慮する必要があります。その価値も!!!! IE：F1がnullの場合

  • いくつかのソケット機能を追加します：非同期TCP/IPサーバー

-レコードを削除する場合は、今すぐファイルのサイズを変更しないでください。削除済みとしてマークします。ここでもいくつかのメトリックを実行する必要があります。未使用スペース>xおよびトランザクション=0の場合、データベースロックを実行し、ポインターを再割り当てしてから、データベースのサイズを変更します。DBファイルにいくつかのスペースが表示されます。データベースロックの代わりにページロックを試みることができます...物事は続行でき、誰も怪我をすることはありません.... DBの最後のロック解除されたページを測定し、ロックします。あなたがあなたのページで埋めることができる削除されたページをチェックしてください。見つかりません、ロックを解除します。見つかった場合は、新しい位置に移動し、ポインタを修正し、古いページを削除済みとしてマークし、ファイルのサイズを変更し、ロックを解除します。なぜそんなに多くの操作？ログを整形式に保つために!!!! ページを小さなページに分割することはできますが、断片化が発生します（ああ...スピードコマンダーを失いましたか？）...2つのアルゴリズムがここにあります。ベストフィット、ワーストフィット....グーグルで。最高は...。

そして、これらすべてを解決すると、「DAM、I DID A DATABASE ... IM GONA NAMEITORACLE!!!!」と大声で叫ぶことができます。; P

于 2012-07-06T10:13:57.057 に答える