2

親ノードへのポインタを追加して、分割および挿入プロセスを簡素化すると、大きな影響がありますか?

一般ノードは次のようになります。

class BPTreeNode{
    bool leaf;
    BPTreeNode *next;
    BPTreeNode *parent; //add-on
    std::vector < int* >pointers;
    std::vector < int >keys;
};

現在、実際のデータベース システムで発生する可能性のある課題は何ですか。

私は趣味のプロジェクトとしてのみ実装しています。

4

1 に答える 1

1

私が考えることができる2つの理由があります：

  1. B+tree から値を削除するアルゴリズムにより、子ブロックが少なすぎる内部ブロック A が生成される場合があります。この違反を解決するために、A の左側または右側のブロックが A にエントリを渡すことができない場合、ブロック A は兄弟ブロック B にマージする必要があります。つまり、ブロック A のすべての子ブロックは、親ポインターがブロック B に更新されました。これは、削除操作で更新が必要なブロックの数を (大幅に) 増やす追加作業です。

  2. これは、標準の B+Tree 操作を実行するために実際には必要ない余分なスペースを表します。B+Tree を介して値を検索する場合、そのリーフ レベルへのパスを簡単に追跡し、それを使用してツリーを上方に遡ることができます。

于 2019-09-07T15:15:41.560 に答える