B樹使用哪種數據結構做節點？

根據Knuth的定義，m階一個B樹（最大許多兒童爲每個節點的）是滿足下列性質的樹：B樹使用哪種數據結構做節點？

（1）每個節點具有大多數的孩子。（2）每個節點（根除外）至少有m/2個子節點。

（3）如果根目錄不是葉節點，則根目錄至少有兩個子目錄。（4）k個孩子的非葉子節點包含k-1個密鑰。

（5）所有葉子都出現在同一級別，並攜帶信息。

來源：Wikipedia

B-樹中的某些可視化是這樣的：

從該可視化，我認爲每個節點具有一個數組數據結構（或至少相似的東西）。

別人看是這樣的：

這看起來而不是作爲一個列表類似的數據結構。

所以我的問題是：

做B樹使用哪些數據結構？

在我的算法類中使用的例子是數據庫和文件系統。有誰知道SQLite如何實現B-樹節點？或ext3？或者任何其他（衆所周知的）真實世界的例子？

來源

2012-07-27 Martin Thoma

有B樹和B +樹。前者用關聯的鍵存儲值。後來在樹葉中重複鍵和存儲值。 – didierc 2012-10-28 22:29:06

SQLite B-tree的實現在1.5節中有詳細描述：https：//www.sqlite.org/fileformat2.html – bsa 2015-06-26 15:59:43

B-Tree本身就是數據結構（也是一種索引結構）。下面是一個僞代碼例子（沒有必要方法和一些必要的定義，這是一個很好的練習吧！）：

節點的身體：

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

    public BNode() {} 

    public BNode() {} 

    public int getValue(int key) {} 

    public BNode getChildren(int key) {} 
}

和B樹的身體：

class BTree 
{ 
    BNode root; 

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

    BNode search(int key) {} 

    void insert(int key) {} 

    void delete(int key) {} 
}

在現實世界中：

的Here is the B-Tree implementation用於索引數據庫的PostgreSQL。

來源

2015-10-24 09:47:52 zwergmaster

B樹使用哪種數據結構做節點？

回答

相關問題