[科普中國]-n叉樹

二叉樹中每個結(jié)點有一個數(shù)據(jù)項,最多有兩個子節(jié)點,如果允許樹的每個節(jié)點可以有兩個以上的子節(jié)點,那么這個樹就稱為n階的多叉樹，或者稱為n叉樹。

每個節(jié)點有m個子節(jié)點和m-1個鍵值。

每個節(jié)點中的鍵值按升序排列。

前i個子節(jié)點中的鍵值都小于地i個鍵值。

后m-1個子節(jié)點中的鍵值都大于第i個鍵值。1

典型的n叉樹有2-3-4-Tree和B-Tree兩種。

B樹（B-tree）是有Bayer和McCreight在1972年提出的數(shù)據(jù)結(jié)構(gòu)。B樹索引是數(shù)據(jù)庫中存取和查找文件(稱為記錄或鍵值)的一種方法，應(yīng)用于磁盤讀取方面。

B樹（B-tree）是一種樹狀數(shù)據(jù)結(jié)構(gòu)，它能夠存儲數(shù)據(jù)、對其進行排序并允許以O(shè)(log n)的時間復(fù)雜度運行進行查找、順序讀取、插入和刪除的數(shù)據(jù)結(jié)構(gòu)。B樹，概括來說是一個節(jié)點可以擁有多于2個子節(jié)點的二叉查找樹。與自平衡二叉查找樹不同，B樹為系統(tǒng)最優(yōu)化大塊數(shù)據(jù)的讀和寫操作。B-tree算法減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度。普遍運用在數(shù)據(jù)庫和文件系統(tǒng)。

B樹的一些性質(zhì)

根據(jù)Knuth's的定義，n階B樹（a B-tree of order n）是具有以下性質(zhì)：

每個點最多有n個孩子

每個非葉子節(jié)點（根節(jié)點除外）最多有n/2(向上取整)個孩子

root至少有2個子樹，除非root的孩子是葉子節(jié)點

k個孩子的非葉子節(jié)點含有k-1個鍵值

所有的葉子節(jié)點都在同一層，并且內(nèi)部節(jié)點不攜帶任何信息。（B樹的階指最大子節(jié)點數(shù)。優(yōu)勢，n階的B樹節(jié)點定義為有k個鍵值和k+1個指針，其中nnode->keyTally||node->keys[i-1]>K)        return BTreeSearch(K,node->pointers[i-1]);      else        return node;    }    else       return 0;  }    B樹的插入

偽代碼如下：