[科普中國(guó)]-n叉樹

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

每個(gè)節(jié)點(diǎn)有m個(gè)子節(jié)點(diǎn)和m-1個(gè)鍵值。

每個(gè)節(jié)點(diǎn)中的鍵值按升序排列。

前i個(gè)子節(jié)點(diǎn)中的鍵值都小于地i個(gè)鍵值。

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

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

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

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

B樹的一些性質(zhì)

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

每個(gè)點(diǎn)最多有n個(gè)孩子

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

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

k個(gè)孩子的非葉子節(jié)點(diǎn)含有k-1個(gè)鍵值

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

偽代碼如下：