3

Knuth の定義によると、次数 m (各ノードの子の最大数) の B ツリーは、次のプロパティを満たすツリーです。

(1) すべてのノードは最大で m 個の子を持ちます。

(2) すべてのノード (ルートを除く) には、少なくとも ⌈m⁄2⌉ の子があります。

(3) ルートがリーフ ノードでない場合、ルートには少なくとも 2 つの子があります。

(4) k 個の子を持つ非リーフ ノードには、k-1 個のキーが含まれます。

(5) すべての葉は同じレベルに現れ、情報を運ぶ。

出典：ウィキペディア

B ツリーのいくつかの視覚化は次のようになります。

ここに画像の説明を入力

この視覚化から、各ノードには配列データ構造 (または少なくとも同様のもの) があると思います。

その他は次のようになります。 ここに画像の説明を入力

これはリストのようなデータ構造のように見えます。

だから私の質問は：

Bツリーはどのデータ構造を使用しますか?

私のアルゴリズム クラスでの使用例は、データベースとファイル システムでした。SQLiteが B ツリー ノードを実装する方法を知っている人はいますか? またはext3？または、他の（よく知られている）実世界の例はありますか？

4

1 に答える 1

0

Bツリー自体がデータ構造です（インデックス構造でもあります）。以下は疑似コードの例です (必要なメソッドと必要な定義がなくても、これは良い例です!):

ノードの本体:

class BNode
{
    int keys[];
    BNode children[];

    public BNode() {}

    public BNode() {}

    public int getValue(int key) {}

    public BNode getChildren(int key) {}
}

そして、B-Tree の本体:

class BTree
{
    BNode root;

    BTree()
    {
        root = new BNode(null);
    }

    BNode search(int key) {}

    void insert(int key) {}

    void delete(int key) {}
}

現実の世界では:

これは、データベースのインデックス作成に使用される PostgreSQLの B-Tree 実装です。

于 2015-10-24T09:47:52.973 に答える