B树、B+树、B*树谈到R 树
轉(zhuǎn)自：?https://blog.csdn.net/v_JULY_v/article/details/6530142
?
從B 樹、B+ 樹、B* 樹談到R 樹
?
作者：July、weedge、Frankie。編程藝術(shù)室出品。
說明：本文從B樹開始談起，然后論述B+樹、B*樹，最后談到R 樹。其中B樹、B+樹及B*樹部分由weedge完成，R 樹部分由Frankie完成，全文最終由July統(tǒng)稿修訂完成。
出處：http://blog.csdn.net/v_JULY_v?。
?
第一節(jié)、B樹、B+樹、B*樹
1.前言：
動(dòng)態(tài)查找樹主要有：二叉查找樹（Binary Search Tree），平衡二叉查找樹（Balanced Binary Search Tree），紅黑樹(Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找樹結(jié)構(gòu)，其查找的時(shí)間復(fù)雜度O(log2N)與樹的深度相關(guān)，那么降低樹的深度自然會(huì)提高查找效率。
但是咱們有面對(duì)這樣一個(gè)實(shí)際問題：就是大規(guī)模數(shù)據(jù)存儲(chǔ)中，實(shí)現(xiàn)索引查詢這樣一個(gè)實(shí)際背景下，樹節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量是有限的（如果元素?cái)?shù)量非常多的話，查找就退化成節(jié)點(diǎn)內(nèi)部的線性查找了），這樣導(dǎo)致二叉查找樹結(jié)構(gòu)由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進(jìn)而導(dǎo)致查詢效率低下（為什么會(huì)出現(xiàn)這種情況，待會(huì)在外部存儲(chǔ)器-磁盤中有所解釋），那么如何減少樹的深度（當(dāng)然是不能減少查詢的數(shù)據(jù)量），一個(gè)基本的想法就是：采用多叉樹結(jié)構(gòu)（由于樹節(jié)點(diǎn)元素?cái)?shù)量是有限的，自然該節(jié)點(diǎn)的子樹數(shù)量也就是有限的）。
也就是說，因?yàn)榇疟P的操作費(fèi)時(shí)費(fèi)資源，如果過于頻繁的多次查找勢(shì)必效率低下。那么如何提高效率，即如何避免磁盤過于頻繁的多次查找呢？根據(jù)磁盤查找存取的次數(shù)往往由樹的高度所決定，所以，只要我們通過某種較好的樹結(jié)構(gòu)減少樹的結(jié)構(gòu)盡量減少樹的高度，那么是不是便能有效減少磁盤查找存取的次數(shù)呢？那這種有效的樹結(jié)構(gòu)是一種怎樣的樹呢？
這樣我們就提出了一個(gè)新的查找樹結(jié)構(gòu)——多路查找樹。根據(jù)平衡二叉樹的啟發(fā)，自然就想到平衡多路查找樹結(jié)構(gòu)，也就是這篇文章所要闡述的第一個(gè)主題B~tree，即B樹結(jié)構(gòu)(后面，我們將看到，B樹的各種操作能使B樹保持較低的高度，從而達(dá)到有效避免磁盤過于頻繁的查找存取操作，從而有效提高查找效率)。
B-tree（B-tree樹即B樹，B即Balanced，平衡的意思）這棵神奇的樹是在Rudolf Bayer,?Edward M. McCreight(1970)寫的一篇論文《Organization and Maintenance of Large Ordered Indices》中首次提出的（wikipedia中：http://en.wikipedia.org/wiki/B-tree，闡述了B-tree名字來源以及相關(guān)的開源地址）。
在開始介紹B~tree之前，先了解下相關(guān)的硬件知識(shí)，才能很好的了解為什么需要B~tree這種外存數(shù)據(jù)結(jié)構(gòu)。?
?
2.外存儲(chǔ)器—磁盤
計(jì)算機(jī)存儲(chǔ)設(shè)備一般分為兩種：內(nèi)存儲(chǔ)器(main memory)和外存儲(chǔ)器(external memory)。 內(nèi)存存取速度快，但容量小，價(jià)格昂貴，而且不能長(zhǎng)期保存數(shù)據(jù)(在不通電情況下數(shù)據(jù)會(huì)消失)。
外存儲(chǔ)器—磁盤是一種直接存取的存儲(chǔ)設(shè)備(DASD)。它是以存取時(shí)間變化不大為特征的?？梢灾苯哟嫒∪魏巫址M，且容量大、速度較其它外存設(shè)備更快。
2.1磁盤的構(gòu)造
磁盤是一個(gè)扁平的圓盤(與電唱機(jī)的唱片類似)。盤面上有許多稱為磁道的圓圈，數(shù)據(jù)就記錄在這些磁道上。磁盤可以是單片的，也可以是由若干盤片組成的盤組，每一盤片上有兩個(gè)面。如下圖11.3中所示的6片盤組為例，除去最頂端和最底端的外側(cè)面不存儲(chǔ)數(shù)據(jù)之外，一共有10個(gè)面可以用來保存信息。
???????????????????????????
?
當(dāng)磁盤驅(qū)動(dòng)器執(zhí)行讀/寫功能時(shí)。盤片裝在一個(gè)主軸上，并繞主軸高速旋轉(zhuǎn)，當(dāng)磁道在讀/寫頭(又叫磁頭) 下通過時(shí)，就可以進(jìn)行數(shù)據(jù)的讀 / 寫了。
一般磁盤分為固定頭盤(磁頭固定)和活動(dòng)頭盤。固定頭盤的每一個(gè)磁道上都有獨(dú)立的磁頭，它是固定不動(dòng)的，專門負(fù)責(zé)這一磁道上數(shù)據(jù)的讀/寫。
活動(dòng)頭盤 (如上圖)的磁頭是可移動(dòng)的。每一個(gè)盤面上只有一個(gè)磁頭(磁頭是雙向的，因此正反盤面都能讀寫)。它可以從該面的一個(gè)磁道移動(dòng)到另一個(gè)磁道。所有磁頭都裝在同一個(gè)動(dòng)臂上，因此不同盤面上的所有磁頭都是同時(shí)移動(dòng)的(行動(dòng)整齊劃一)。當(dāng)盤片繞主軸旋轉(zhuǎn)的時(shí)候，磁頭與旋轉(zhuǎn)的盤片形成一個(gè)圓柱體。各個(gè)盤面上半徑相同的磁道組成了一個(gè)圓柱面，我們稱為柱面 。因此，柱面的個(gè)數(shù)也就是盤面上的磁道數(shù)。?
2.2磁盤的讀/寫原理和效率
磁盤上數(shù)據(jù)必須用一個(gè)三維地址唯一標(biāo)示：柱面號(hào)、盤面號(hào)、塊號(hào)(磁道上的盤塊)。
讀/寫磁盤上某一指定數(shù)據(jù)需要下面3個(gè)步驟：
(1)??首先移動(dòng)臂根據(jù)柱面號(hào)使磁頭移動(dòng)到所需要的柱面上，這一過程被稱為定位或查找 。
(2)??如上圖11.3中所示的6盤組示意圖中，所有磁頭都定位到了10個(gè)盤面的10條磁道上(磁頭都是雙向的)。這時(shí)根據(jù)盤面號(hào)來確定指定盤面上的磁道。
(3) 盤面確定以后，盤片開始旋轉(zhuǎn)，將指定塊號(hào)的磁道段移動(dòng)至磁頭下。
經(jīng)過上面三個(gè)步驟，指定數(shù)據(jù)的存儲(chǔ)位置就被找到。這時(shí)就可以開始讀/寫操作了。
訪問某一具體信息，由3部分時(shí)間組成：
● 查找時(shí)間(seek time) Ts: 完成上述步驟(1)所需要的時(shí)間。這部分時(shí)間代價(jià)最高，最大可達(dá)到0.1s左右。
● 等待時(shí)間(latency time) Tl: 完成上述步驟(3)所需要的時(shí)間。由于盤片繞主軸旋轉(zhuǎn)速度很快，一般為7200轉(zhuǎn)/分(電腦硬盤的性能指標(biāo)之一, 家用的普通硬盤的轉(zhuǎn)速一般有5400rpm(筆記本)、7200rpm幾種)。因此一般旋轉(zhuǎn)一圈大約0.0083s。
● 傳輸時(shí)間(transmission time) Tt: 數(shù)據(jù)通過系統(tǒng)總線傳送到內(nèi)存的時(shí)間，一般傳輸一個(gè)字節(jié)(byte)大概0.02us=2*10^(-8)s
磁盤讀取數(shù)據(jù)是以盤塊(block)為基本單位的。位于同一盤塊中的所有數(shù)據(jù)都能被一次性全部讀取出來。而磁盤IO代價(jià)主要花費(fèi)在查找時(shí)間Ts上。因此我們應(yīng)該盡量將相關(guān)信息存放在同一盤塊，同一磁道中?；蛘咧辽俜旁谕恢婊蛳噜徶嫔?#xff0c;以求在讀/寫信息時(shí)盡量減少磁頭來回移動(dòng)的次數(shù)，避免過多的查找時(shí)間Ts。
所以，在大規(guī)模數(shù)據(jù)存儲(chǔ)方面，大量數(shù)據(jù)存儲(chǔ)在外存磁盤中，而在外存磁盤中讀取/寫入塊(block)中某數(shù)據(jù)時(shí)，首先需要定位到磁盤中的某塊，如何有效地查找磁盤中的數(shù)據(jù)，需要一種合理高效的外存數(shù)據(jù)結(jié)構(gòu)，就是下面所要重點(diǎn)闡述的B-tree結(jié)構(gòu)，以及相關(guān)的變種結(jié)構(gòu)：B+-tree結(jié)構(gòu)和B*-tree結(jié)構(gòu)。
3.B- 樹?
?????3.1什么是B-樹
具體講解之前，有一點(diǎn)，再次強(qiáng)調(diào)下：B-樹，即為B樹。因?yàn)锽樹的原英文名稱為B-tree，而國(guó)內(nèi)很多人喜歡把B-tree譯作B-樹，其實(shí)，這是個(gè)非常不好的直譯，很容易讓人產(chǎn)生誤解。如人們可能會(huì)以為B-樹是一種樹，而B樹又是一種一種樹。而事實(shí)上是，B-tree就是指的B樹。特此說明。
我們知道，B 樹是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉（下面你會(huì)看到，相對(duì)于二叉，B樹每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支，即多叉）平衡查找樹。與本blog之前介紹的紅黑樹很相似，但在降低磁盤I/0操作方面要更好一些。許多數(shù)據(jù)庫(kù)系統(tǒng)都一般使用B樹或者B樹的各種變形結(jié)構(gòu)，如下文即將要介紹的B+樹，B*樹來存儲(chǔ)信息。
?B樹與紅黑樹最大的不同在于，B樹的結(jié)點(diǎn)可以有許多子女，從幾個(gè)到幾千個(gè)。那為什么又說B樹與紅黑樹很相似呢?因?yàn)榕c紅黑樹一樣，一棵含n個(gè)結(jié)點(diǎn)的B樹的高度也為O（lgn），但可能比一棵紅黑樹的高度小許多，應(yīng)為它的分支因子比較大。所以，B樹可以在O（logn）時(shí)間內(nèi)，實(shí)現(xiàn)各種如插入（insert），刪除（delete）等動(dòng)態(tài)集合操作。
如下圖所示，即是一棵B樹，一棵關(guān)鍵字為英語中輔音字母的B樹，現(xiàn)在要從樹種查找字母R（包含n[x]個(gè)關(guān)鍵字的內(nèi)結(jié)點(diǎn)x，x有n[x]+1]個(gè)子女（也就是說，一個(gè)內(nèi)結(jié)點(diǎn)x若含有n[x]個(gè)關(guān)鍵字，那么x將含有n[x]+1個(gè)子女）。所有的葉結(jié)點(diǎn)都處于相同的深度，帶陰影的結(jié)點(diǎn)為查找字母R時(shí)要檢查的結(jié)點(diǎn)）：
?
相信，從上圖你能輕易的看到，一個(gè)內(nèi)結(jié)點(diǎn)x若含有n[x]個(gè)關(guān)鍵字，那么x將含有n[x]+1個(gè)子女。如含有2個(gè)關(guān)鍵字D H的內(nèi)結(jié)點(diǎn)有3個(gè)子女，而含有3個(gè)關(guān)鍵字Q T X的內(nèi)結(jié)點(diǎn)有4個(gè)子女。
????B樹的定義，從下文中，你將看到，或者是用階，或者是用度，如下段文字所述：
????Unfortunately, the literature on B-trees is not uniform in its use of terms relating to B-Trees. (Folk & Zoellick 1992, p. 362)?Bayer & McCreight (1972), Comer (1979), and others define the order of B-tree as the minimum number of keys in a non-root node. Folk & Zoellick (1992) points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys. (Knuth 1998,TAOCP p. 483) avoids the problem by defining the order to be maximum number of children (which is one more than the maximum number of keys).
????from: http://en.wikipedia.org/wiki/Btree#Technical_description。
????用階定義的B樹
????B 樹又叫平衡多路查找樹。一棵m階的B 樹 (注：切勿簡(jiǎn)單的認(rèn)為一棵m階的B樹是m叉樹，雖然存在四叉樹，八叉樹，KD樹，及vp/R樹/R*樹/R+樹/X樹/M樹/線段樹/希爾伯特R樹/優(yōu)先R樹等空間劃分樹，但與B樹完全不等同)的特性如下：
樹中每個(gè)結(jié)點(diǎn)最多含有m個(gè)孩子（m>=2）；
除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子（特殊情況：沒有孩子的根結(jié)點(diǎn)，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，整棵樹只有一個(gè)根節(jié)點(diǎn)）；
所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部接點(diǎn)或查詢失敗的接點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針都為null)；（讀者反饋@冷岳：這里有錯(cuò)，葉子節(jié)點(diǎn)只是沒有孩子和指向孩子的指針，這些節(jié)點(diǎn)也存在，也有元素。@研究者July：其實(shí)，關(guān)鍵是把什么當(dāng)做葉子結(jié)點(diǎn)，因?yàn)槿缂t黑樹中，每一個(gè)NULL指針即當(dāng)做葉子結(jié)點(diǎn)，只是沒畫出來而已）。
每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
???????a)???Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序K(i-1)< Ki。?
???????b)???Pi為指向子樹根的接點(diǎn)，且指針P(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)。?
???????c)???關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1。如下圖所示：
????用度定義的B樹
??????針對(duì)上面的5點(diǎn)，再闡述下：B樹中每一個(gè)結(jié)點(diǎn)能包含的關(guān)鍵字（如之前上面的D H和Q T X）數(shù)有一個(gè)上界和下界。這個(gè)下界可以用一個(gè)稱作B樹的最小度數(shù)（算法導(dǎo)論中文版上譯作度數(shù)，最小度數(shù)即內(nèi)節(jié)點(diǎn)中節(jié)點(diǎn)最小孩子數(shù)目）m（m>=2）表示。
每個(gè)非根的內(nèi)結(jié)點(diǎn)至多有m個(gè)子女，每個(gè)非根的結(jié)點(diǎn)必須至少含有m-1個(gè)關(guān)鍵字，如果樹是非空的，則根結(jié)點(diǎn)至少包含一個(gè)關(guān)鍵字；
每個(gè)結(jié)點(diǎn)可包含至多2m-1個(gè)關(guān)鍵字。所以一個(gè)內(nèi)結(jié)點(diǎn)至多可有2m個(gè)子女。如果一個(gè)結(jié)點(diǎn)恰好有2m-1個(gè)關(guān)鍵字，我們就說這個(gè)結(jié)點(diǎn)是滿的（而稍后介紹的B*樹作為B樹的一種常用變形，B*樹中要求每個(gè)內(nèi)結(jié)點(diǎn)至少為2/3滿，而不是像這里的B樹所要求的至少半滿）；
當(dāng)關(guān)鍵字?jǐn)?shù)m=2（t=2的意思是，mmin=2，m可以>=2）時(shí)的B樹是最簡(jiǎn)單的（有很多人會(huì)因此誤認(rèn)為B樹就是二叉查找樹，但二叉查找樹就是二叉查找樹，B樹就是B樹，B樹是一棵含有m（m>=2）個(gè)關(guān)鍵字的平衡多路查找樹），此時(shí)，每個(gè)內(nèi)結(jié)點(diǎn)可能因此而含有2個(gè)、3個(gè)或4個(gè)子女，亦即一棵2-3-4樹，然而在實(shí)際中，通常采用大得多的t值。
????B樹中的每個(gè)結(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支(當(dāng)然是不能超過磁盤塊的大小，根據(jù)磁盤驅(qū)動(dòng)(disk drives)的不同，一般塊的大小在1k~4k左右)；這樣樹的深度降低了，這就意味著查找一個(gè)元素只要很少結(jié)點(diǎn)從外存磁盤中讀入內(nèi)存，很快訪問到要查找的數(shù)據(jù)。如果你看完上面關(guān)于B樹定義的介紹，思維感覺不夠清晰，請(qǐng)繼續(xù)參閱下文第6小節(jié)、B樹的插入、刪除操作 部分。
????3.2B樹的類型和節(jié)點(diǎn)定義
????B樹的類型和節(jié)點(diǎn)定義如下圖所示：
?
?
????3.3文件查找的具體過程(涉及磁盤IO操作)
為了簡(jiǎn)單，這里用少量數(shù)據(jù)構(gòu)造一棵3叉樹的形式，實(shí)際應(yīng)用中的B樹結(jié)點(diǎn)中關(guān)鍵字很多的。上面的圖中比如根結(jié)點(diǎn)，其中17表示一個(gè)磁盤文件的文件名；小紅方塊表示這個(gè)17文件內(nèi)容在硬盤中的存儲(chǔ)位置；p1表示指向17左子樹的指針。
其結(jié)構(gòu)可以簡(jiǎn)單定義為：
typedef struct {
????/*文件數(shù)*/
????int??file_num;
????/*文件名(key)*/
????char * file_name[max_file_num];
????/*指向子節(jié)點(diǎn)的指針*/
?????BTNode * BTptr[max_file_num+1];
?????/*文件在硬盤中的存儲(chǔ)位置*/
?????FILE_HARD_ADDR offset[max_file_num];
}BTNode;
假如每個(gè)盤塊可以正好存放一個(gè)B樹的結(jié)點(diǎn)（正好存放2個(gè)文件名）。那么一個(gè)BTNODE結(jié)點(diǎn)就代表一個(gè)盤塊，而子樹指針就是存放另外一個(gè)盤塊的地址。
下面，咱們來模擬下查找文件29的過程：
根據(jù)根結(jié)點(diǎn)指針找到文件目錄的根磁盤塊1，將其中的信息導(dǎo)入內(nèi)存?！敬疟PIO操作 1次】????
此時(shí)內(nèi)存中有兩個(gè)文件名17、35和三個(gè)存儲(chǔ)其他磁盤頁(yè)面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：17<29<35，因此我們找到指針p2。
根據(jù)p2指針，我們定位到磁盤塊3，并將其中的信息導(dǎo)入內(nèi)存?！敬疟PIO操作 2次】????
此時(shí)內(nèi)存中有兩個(gè)文件名26，30和三個(gè)存儲(chǔ)其他磁盤頁(yè)面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)：26<29<30，因此我們找到指針p2。
根據(jù)p2指針，我們定位到磁盤塊8，并將其中的信息導(dǎo)入內(nèi)存?！敬疟PIO操作 3次】????
此時(shí)內(nèi)存中有兩個(gè)文件名28，29。根據(jù)算法我們查找到文件名29，并定位了該文件內(nèi)存的磁盤地址。
分析上面的過程，發(fā)現(xiàn)需要3次磁盤IO操作和3次內(nèi)存查找操作。關(guān)于內(nèi)存中的文件名查找，由于是一個(gè)有序表結(jié)構(gòu)，可以利用折半查找提高效率。至于IO操作是影響整個(gè)B樹查找效率的決定因素。
當(dāng)然，如果我們使用平衡二叉樹的磁盤存儲(chǔ)結(jié)構(gòu)來進(jìn)行查找，磁盤4次，最多5次，而且文件越多，B樹比平衡二叉樹所用的磁盤IO操作次數(shù)將越少，效率也越高。
3.4B樹的高度
????根據(jù)上面的例子我們可以看出，對(duì)于輔存做IO讀的次數(shù)取決于B樹的高度。而B樹的高度由什么決定的呢？
????若B樹某一非葉子節(jié)點(diǎn)包含N個(gè)關(guān)鍵字，則此非葉子節(jié)點(diǎn)含有N+1個(gè)孩子結(jié)點(diǎn)，而所有的葉子結(jié)點(diǎn)都在第I層，我們可以得出：
因?yàn)楦辽儆袃蓚€(gè)孩子，因此第2層至少有兩個(gè)結(jié)點(diǎn)。
除根和葉子外，其它結(jié)點(diǎn)至少有┌m/2┐個(gè)孩子，
因此在第3層至少有2*┌m/2┐個(gè)結(jié)點(diǎn)，
在第4層至少有2*(┌m/2┐^2)個(gè)結(jié)點(diǎn)，
在第 I 層至少有2*(┌m/2┐^(l-2) )個(gè)結(jié)點(diǎn)，于是有：?N+1 ≥ 2*┌m/2┐I-2；
考慮第L層的結(jié)點(diǎn)個(gè)數(shù)為N+1，那么2*(┌m/2┐^(l-2)）≤N+1，也就是L層的最少結(jié)點(diǎn)數(shù)剛好達(dá)到N+1個(gè)，即： I≤ log┌m/2┐((N+1)/2 )+2；
所以
當(dāng)B樹包含N個(gè)關(guān)鍵字時(shí)，B樹的最大高度為l-1（因?yàn)橛?jì)算B樹高度時(shí)，葉結(jié)點(diǎn)所在層不計(jì)算在內(nèi)），即：l - 1 =?log┌m/2┐((N+1)/2 )+1。
這個(gè)B樹的高度公式從側(cè)面顯示了B樹的查找效率是相當(dāng)高的。
曾在一次面試中被問到，一棵含有N個(gè)總關(guān)鍵字?jǐn)?shù)的m階的B樹的最大高度是多少?答曰：log_ceil（m/2）(N+1)/2?+ 1 （上面中關(guān)于m階B樹的第1點(diǎn)特性已經(jīng)提到：樹中每個(gè)結(jié)點(diǎn)含有最多含有m個(gè)孩子，即m滿足：ceil(m/2)<=m<=m。而樹中每個(gè)結(jié)點(diǎn)含孩子數(shù)越少，樹的高度則越大，故如此）。在2012微軟4月份的筆試中也問到了此問題。
此外，還有讀者反饋，說上面的B樹的高度計(jì)算公式與算法導(dǎo)論一書上的不同，而后我特意翻看了算法導(dǎo)論第18章關(guān)于B樹的高度一節(jié)的內(nèi)容，如下圖所示：
在上圖中書上所舉的例子中，也許，根據(jù)我們大多數(shù)人的理解，它的高度應(yīng)該是4，而書上卻說的是“一棵高度為3的B樹”。我想，此時(shí)，你也就明白了，算法導(dǎo)論一書上的高度的定義是從“0”開始計(jì)數(shù)的，而我們中國(guó)人的習(xí)慣是樹的高度是從“1”開始計(jì)數(shù)的。特此說明。July、二零一二年九月二十七日。
4.B+-tree
B+-tree：是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B-tree的變形樹。
一棵m階的B+樹和m階的B樹的異同點(diǎn)在于：
??????1.有n棵子樹的結(jié)點(diǎn)中含有n-1?個(gè)關(guān)鍵字；?(此處頗有爭(zhēng)議，B+樹到底是與B 樹n棵子樹有n-1個(gè)關(guān)鍵字 保持一致，還是不一致：B樹n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字，待后續(xù)查證。暫先提供兩個(gè)參考鏈接：①wikipedia?http://en.wikipedia.org/wiki/B%2B_tree#Overview；②http://hedengcheng.com/?p=525。而下面B+樹的圖尚未最終確定是否有問題，請(qǐng)讀者注意)
??????2.所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。 (而B 樹的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息)
??????3.所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最小）關(guān)鍵字。 (而B 樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)
?
?
a)?????為什么說B+-tree比B 樹更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫(kù)索引？
1) B+-tree的磁盤讀寫代價(jià)更低
B+-tree的內(nèi)部結(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針。因此其內(nèi)部結(jié)點(diǎn)相對(duì)B 樹更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對(duì)來說IO讀寫次數(shù)也就降低了。
????舉個(gè)例子，假設(shè)磁盤中的一個(gè)盤塊容納16bytes，而一個(gè)關(guān)鍵字2bytes，一個(gè)關(guān)鍵字具體信息指針2bytes。一棵9階B-tree(一個(gè)結(jié)點(diǎn)最多8個(gè)關(guān)鍵字)的內(nèi)部結(jié)點(diǎn)需要2個(gè)盤快。而B+ 樹內(nèi)部結(jié)點(diǎn)只需要1個(gè)盤快。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候，B 樹就比B+ 樹多一次盤塊查找時(shí)間(在磁盤中就是盤片旋轉(zhuǎn)的時(shí)間)。
2) B+-tree的查詢效率更加穩(wěn)定
由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路。所有關(guān)鍵字查詢的路徑長(zhǎng)度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。
讀者點(diǎn)評(píng)
本文評(píng)論下第149樓，fanyy1991針對(duì)上文所說的兩點(diǎn)，道：個(gè)人覺得這兩個(gè)原因都不是主要原因。數(shù)據(jù)庫(kù)索引采用B+樹的主要原因是 B樹在提高了磁盤IO性能的同時(shí)并沒有解決元素遍歷的效率低下的問題。正是為了解決這個(gè)問題，B+樹應(yīng)運(yùn)而生。B+樹只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫(kù)中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作（或者說效率太低）。
b)????B+-tree的應(yīng)用: VSAM(虛擬存儲(chǔ)存取法)文件(來源論文 the ubiquitous Btree 作者：D COMER - 1979 )
?
?
5.B*-tree
B*-tree是B+-tree的變體，在B+樹的基礎(chǔ)上(所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針)，B*樹中非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）。給出了一個(gè)簡(jiǎn)單實(shí)例，如下圖所示：
?
B+樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針。
B*樹的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針。
所以，B*樹分配新結(jié)點(diǎn)的概率比B+樹要低，空間使用率更高；
?
6、B樹的插入、刪除操作
上面第3小節(jié)簡(jiǎn)單介紹了利用B樹這種結(jié)構(gòu)如何訪問外存磁盤中的數(shù)據(jù)的情況，下面咱們通過另外一個(gè)實(shí)例來對(duì)這棵B樹的插入（insert）,刪除（delete）基本操作進(jìn)行詳細(xì)的介紹。
但在此之前，咱們還得簡(jiǎn)單回顧下一棵m階的B 樹的特性，如下：
樹中每個(gè)結(jié)點(diǎn)含有最多含有m個(gè)孩子，即m滿足：ceil(m/2)<=m<=m。
除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有[ceil(m / 2)]個(gè)孩子（其中ceil(x)是一個(gè)取上限的函數(shù)）；
若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子（特殊情況：沒有孩子的根結(jié)點(diǎn)，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，整棵樹只有一個(gè)根節(jié)點(diǎn)）；
所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部接點(diǎn)或查詢失敗的接點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針都為null)；
每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
???????a)???Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序K(i-1)< Ki。?
???????b)???Pi為指向子樹根的接點(diǎn)，且指針P(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)。?
???????c)???除根結(jié)點(diǎn)之外的結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)n必須滿足： [ceil(m / 2)-1]<= n <= m-1（葉子結(jié)點(diǎn)也必須滿足此條關(guān)于關(guān)鍵字?jǐn)?shù)的性質(zhì)，根結(jié)點(diǎn)除外）。
ok，下面咱們以一棵5階（即樹中任一結(jié)點(diǎn)至多含有4個(gè)關(guān)鍵字，5棵子樹）B樹實(shí)例進(jìn)行講解(如下圖所示)：
備注：關(guān)鍵字?jǐn)?shù)（2-4個(gè)）針對(duì)--非根結(jié)點(diǎn)（包括葉子結(jié)點(diǎn)在內(nèi)），孩子數(shù)（3-5個(gè)）--針對(duì)根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外的內(nèi)結(jié)點(diǎn)。當(dāng)然，根結(jié)點(diǎn)是必須至少有2個(gè)孩子的，不然就成直線型搜索樹了。下圖中，讀者可以看到關(guān)鍵字?jǐn)?shù)2-4個(gè)，內(nèi)結(jié)點(diǎn)孩子數(shù)3-5個(gè)：
關(guān)鍵字為大寫字母，順序?yàn)樽帜干颉?/p>
結(jié)點(diǎn)定義如下：
typedef?struct{
???int?Count;?????????//?當(dāng)前節(jié)點(diǎn)中關(guān)鍵元素?cái)?shù)目
???ItemType?Key[4];???//?存儲(chǔ)關(guān)鍵字元素的數(shù)組
???long?Branch[5];????//?偽指針數(shù)組，(記錄數(shù)目)方便判斷合并和分裂的情況
}?NodeType;
?
6.1、插入（insert）操作
插入一個(gè)元素時(shí)，首先在B樹中是否存在，如果不存在，即在葉子結(jié)點(diǎn)處結(jié)束，然后在葉子結(jié)點(diǎn)中插入該新的元素，注意：如果葉子結(jié)點(diǎn)空間足夠，這里需要向右移動(dòng)該葉子結(jié)點(diǎn)中大于新插入關(guān)鍵字的元素，如果空間滿了以致沒有足夠的空間去添加新的元素，則將該結(jié)點(diǎn)進(jìn)行“分裂”，將一半數(shù)量的關(guān)鍵字元素分裂到新的其相鄰右結(jié)點(diǎn)中，中間關(guān)鍵字元素上移到父結(jié)點(diǎn)中（當(dāng)然，如果父結(jié)點(diǎn)空間滿了，也同樣需要“分裂”操作），而且當(dāng)結(jié)點(diǎn)中關(guān)鍵元素向右移動(dòng)了，相關(guān)的指針也需要向右移。如果在根結(jié)點(diǎn)插入新元素，空間滿了，則進(jìn)行分裂操作，這樣原來的根結(jié)點(diǎn)中的中間關(guān)鍵字元素向上移動(dòng)到新的根結(jié)點(diǎn)中，因此導(dǎo)致樹的高度增加一層。如下圖所示：
1、OK，下面咱們通過一個(gè)實(shí)例來逐步講解下。插入以下字符字母到一棵空的B?樹中（非根結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)小了（小于2個(gè)）就合并，大了（超過4個(gè)）就分裂）：C?N?G?A?H?E?K?Q?M?F?W?L?T?Z?D?P?R?X?Y?S，首先，結(jié)點(diǎn)空間足夠，4個(gè)字母插入相同的結(jié)點(diǎn)中，如下圖：
?
2、當(dāng)咱們?cè)囍迦際時(shí)，結(jié)點(diǎn)發(fā)現(xiàn)空間不夠，以致將其分裂成2個(gè)結(jié)點(diǎn)，移動(dòng)中間元素G上移到新的根結(jié)點(diǎn)中，在實(shí)現(xiàn)過程中，咱們把A和C留在當(dāng)前結(jié)點(diǎn)中，而H和N放置新的其右鄰居結(jié)點(diǎn)中。如下圖：
?
3、當(dāng)咱們插入E,K,Q時(shí)，不需要任何分裂操作
?
?
?
?
?
?
?
?
?
?
?
?
4、插入M需要一次分裂，注意M恰好是中間關(guān)鍵字元素，以致向上移到父節(jié)點(diǎn)中
?
5、插入F,W,L,T不需要任何分裂操作
?
6、插入Z時(shí)，最右的葉子結(jié)點(diǎn)空間滿了，需要進(jìn)行分裂操作，中間元素T上移到父節(jié)點(diǎn)中，注意通過上移中間元素，樹最終還是保持平衡，分裂結(jié)果的結(jié)點(diǎn)存在2個(gè)關(guān)鍵字元素。
?
7、插入D時(shí)，導(dǎo)致最左邊的葉子結(jié)點(diǎn)被分裂，D恰好也是中間元素，上移到父節(jié)點(diǎn)中，然后字母P,R,X,Y陸續(xù)插入不需要任何分裂操作（別忘了，樹中至多5個(gè)孩子）。
?
8、最后，當(dāng)插入S時(shí)，含有N,P,Q,R的結(jié)點(diǎn)需要分裂，把中間元素Q上移到父節(jié)點(diǎn)中，但是情況來了，父節(jié)點(diǎn)中空間已經(jīng)滿了，所以也要進(jìn)行分裂，將父節(jié)點(diǎn)中的中間元素M上移到新形成的根結(jié)點(diǎn)中，注意以前在父節(jié)點(diǎn)中的第三個(gè)指針在修改后包括D和G節(jié)點(diǎn)中。這樣具體插入操作的完成，下面介紹刪除操作，刪除操作相對(duì)于插入操作要考慮的情況多點(diǎn)。
?
6.2、刪除(delete)操作
首先查找B樹中需刪除的元素,如果該元素在B樹中存在，則將該元素在其結(jié)點(diǎn)中進(jìn)行刪除，如果刪除該元素后，首先判斷該元素是否有左右孩子結(jié)點(diǎn)，如果有，則上移孩子結(jié)點(diǎn)中的某相近元素(“左孩子最右邊的節(jié)點(diǎn)”或“右孩子最左邊的節(jié)點(diǎn)”)到父節(jié)點(diǎn)中，然后是移動(dòng)之后的情況；如果沒有，直接刪除后，移動(dòng)之后的情況。
刪除元素，移動(dòng)相應(yīng)元素之后，如果某結(jié)點(diǎn)中元素?cái)?shù)目（即關(guān)鍵字?jǐn)?shù)）小于ceil(m/2)-1，則需要看其某相鄰兄弟結(jié)點(diǎn)是否豐滿（結(jié)點(diǎn)中元素個(gè)數(shù)大于ceil(m/2)-1）（還記得第一節(jié)中關(guān)于B樹的第5個(gè)特性中的c點(diǎn)么?：?c)除根結(jié)點(diǎn)之外的結(jié)點(diǎn)（包括葉子結(jié)點(diǎn)）的關(guān)鍵字的個(gè)數(shù)n必須滿足： （ceil(m / 2)-1）<= n <= m-1。m表示最多含有m個(gè)孩子，n表示關(guān)鍵字?jǐn)?shù)。在本小節(jié)中舉的一顆B樹的示例中，關(guān)鍵字?jǐn)?shù)n滿足：2<=n<=4），如果豐滿，則向父節(jié)點(diǎn)借一個(gè)元素來滿足條件；如果其相鄰兄弟都剛脫貧，即借了之后其結(jié)點(diǎn)數(shù)目小于ceil(m/2)-1，則該結(jié)點(diǎn)與其相鄰的某一兄弟結(jié)點(diǎn)進(jìn)行“合并”成一個(gè)結(jié)點(diǎn)，以此來滿足條件。那咱們通過下面實(shí)例來詳細(xì)了解吧。
以上述插入操作構(gòu)造的一棵5階B樹（樹中最多含有m（m=5）個(gè)孩子，因此關(guān)鍵字?jǐn)?shù)最小為ceil(m / 2)-1=2。還是這句話，關(guān)鍵字?jǐn)?shù)小了（小于2個(gè)）就合并，大了（超過4個(gè)）就分裂）為例，依次刪除H,T,R,E。
1、首先刪除元素H，當(dāng)然首先查找H，H在一個(gè)葉子結(jié)點(diǎn)中，且該葉子結(jié)點(diǎn)元素?cái)?shù)目3大于最小元素?cái)?shù)目ceil(m/2)-1=2，則操作很簡(jiǎn)單，咱們只需要移動(dòng)K至原來H的位置，移動(dòng)L至K的位置（也就是結(jié)點(diǎn)中刪除元素后面的元素向前移動(dòng)）
?
2、下一步，刪除T,因?yàn)門沒有在葉子結(jié)點(diǎn)中，而是在中間結(jié)點(diǎn)中找到，咱們發(fā)現(xiàn)他的繼承者W(字母升序的下個(gè)元素)，將W上移到T的位置，然后將原包含W的孩子結(jié)點(diǎn)中的W進(jìn)行刪除，這里恰好刪除W后，該孩子結(jié)點(diǎn)中元素個(gè)數(shù)大于2，無需進(jìn)行合并操作。
?
3、下一步刪除R，R在葉子結(jié)點(diǎn)中,但是該結(jié)點(diǎn)中元素?cái)?shù)目為2，刪除導(dǎo)致只有1個(gè)元素，已經(jīng)小于最小元素?cái)?shù)目ceil(5/2)-1=2,而由前面我們已經(jīng)知道：如果其某個(gè)相鄰兄弟結(jié)點(diǎn)中比較豐滿（元素個(gè)數(shù)大于ceil(5/2)-1=2），則可以向父結(jié)點(diǎn)借一個(gè)元素，然后將最豐滿的相鄰兄弟結(jié)點(diǎn)中上移最后或最前一個(gè)元素到父節(jié)點(diǎn)中（有沒有看到紅黑樹中左旋操作的影子?），在這個(gè)實(shí)例中，右相鄰兄弟結(jié)點(diǎn)中比較豐滿（3個(gè)元素大于2），所以先向父節(jié)點(diǎn)借一個(gè)元素W下移到該葉子結(jié)點(diǎn)中，代替原來S的位置，S前移；然后X在相鄰右兄弟結(jié)點(diǎn)中上移到父結(jié)點(diǎn)中，最后在相鄰右兄弟結(jié)點(diǎn)中刪除X，后面元素前移。
?
4、最后一步刪除E，?刪除后會(huì)導(dǎo)致很多問題，因?yàn)镋所在的結(jié)點(diǎn)數(shù)目剛好達(dá)標(biāo)，剛好滿足最小元素個(gè)數(shù)（ceil(5/2)-1=2）,而相鄰的兄弟結(jié)點(diǎn)也是同樣的情況，刪除一個(gè)元素都不能滿足條件，所以需要該節(jié)點(diǎn)與某相鄰兄弟結(jié)點(diǎn)進(jìn)行合并操作；首先移動(dòng)父結(jié)點(diǎn)中的元素（該元素在兩個(gè)需要合并的兩個(gè)結(jié)點(diǎn)元素之間）下移到其子結(jié)點(diǎn)中，然后將這兩個(gè)結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)。所以在該實(shí)例中，咱們首先將父節(jié)點(diǎn)中的元素D下移到已經(jīng)刪除E而只有F的結(jié)點(diǎn)中，然后將含有D和F的結(jié)點(diǎn)和含有A,C的相鄰兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)。
?
5、也許你認(rèn)為這樣刪除操作已經(jīng)結(jié)束了，其實(shí)不然，在看看上圖，對(duì)于這種特殊情況，你立即會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)只包含一個(gè)元素G，沒達(dá)標(biāo)（因?yàn)榉歉?jié)點(diǎn)包括葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)n必須滿足于2=<n<=4，而此處的n=1），這是不能夠接受的。如果這個(gè)問題結(jié)點(diǎn)的相鄰兄弟比較豐滿，則可以向父結(jié)點(diǎn)借一個(gè)元素。假設(shè)這時(shí)右兄弟結(jié)點(diǎn)（含有Q,X）有一個(gè)以上的元素（Q右邊還有元素），然后咱們將M下移到元素很少的子結(jié)點(diǎn)中，將Q上移到M的位置，這時(shí)，Q的左子樹將變成M的右子樹，也就是含有N，P結(jié)點(diǎn)被依附在M的右指針上。所以在這個(gè)實(shí)例中，咱們沒有辦法去借一個(gè)元素，只能與兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)，而根結(jié)點(diǎn)中的唯一元素M下移到子結(jié)點(diǎn)，這樣，樹的高度減少一層。
?
為了進(jìn)一步詳細(xì)討論刪除的情況，再舉另外一個(gè)實(shí)例：
這里是一棵不同的5序B樹，那咱們?cè)囍鴦h除C
?
于是將刪除元素C的右子結(jié)點(diǎn)中的D元素上移到C的位置，但是出現(xiàn)上移元素后，只有一個(gè)元素的結(jié)點(diǎn)的情況。
又因?yàn)楹蠩的結(jié)點(diǎn)，其相鄰兄弟結(jié)點(diǎn)才剛脫貧（最少元素個(gè)數(shù)為2），不可能向父節(jié)點(diǎn)借元素，所以只能進(jìn)行合并操作，于是這里將含有A,B的左兄弟結(jié)點(diǎn)和含有E的結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)。
?
這樣又出現(xiàn)只含有一個(gè)元素F結(jié)點(diǎn)的情況，這時(shí)，其相鄰的兄弟結(jié)點(diǎn)是豐滿的（元素個(gè)數(shù)為3>最小元素個(gè)數(shù)2），這樣就可以想父結(jié)點(diǎn)借元素了，把父結(jié)點(diǎn)中的J下移到該結(jié)點(diǎn)中，相應(yīng)的如果結(jié)點(diǎn)中J后有元素則前移，然后相鄰兄弟結(jié)點(diǎn)中的第一個(gè)元素（或者最后一個(gè)元素）上移到父節(jié)點(diǎn)中，后面的元素（或者前面的元素）前移（或者后移）；注意含有K，L的結(jié)點(diǎn)以前依附在M的左邊，現(xiàn)在變?yōu)橐栏皆贘的右邊。這樣每個(gè)結(jié)點(diǎn)都滿足B樹結(jié)構(gòu)性質(zhì)。
?
從以上操作可看出：除根結(jié)點(diǎn)之外的結(jié)點(diǎn)（包括葉子結(jié)點(diǎn)）的關(guān)鍵字的個(gè)數(shù)n滿足：（ceil(m / 2)-1）<= n <= m-1，即2<=n<=4。這也佐證了咱們之前的觀點(diǎn)。刪除操作完。
?
7.總結(jié)
通過以上介紹，大致將B樹，B+樹，B*樹總結(jié)如下：
B樹：有序數(shù)組+平衡多叉樹；
B+樹：有序數(shù)組鏈表+平衡多叉樹；
B*樹：一棵豐滿的B+樹。
????在大規(guī)模數(shù)據(jù)存儲(chǔ)的文件系統(tǒng)中，B~tree系列數(shù)據(jù)結(jié)構(gòu)，起著很重要的作用，對(duì)于存儲(chǔ)不同的數(shù)據(jù)，節(jié)點(diǎn)相關(guān)的信息也是有所不同，這里根據(jù)自己的理解，畫的一個(gè)查找以職工號(hào)為關(guān)鍵字，職工號(hào)為38的記錄的簡(jiǎn)單示意圖。(這里假設(shè)每個(gè)物理塊容納3個(gè)索引，磁盤的I/O操作的基本單位是塊（block),磁盤訪問很費(fèi)時(shí)，采用B+樹有效的減少了訪問磁盤的次數(shù)。）
對(duì)于像MySQL，DB2，Oracle等數(shù)據(jù)庫(kù)中的索引結(jié)構(gòu)得有較深入的了解才行，建議去找一些B 樹相關(guān)的開源代碼研究。
走進(jìn)搜索引擎的作者梁斌老師針對(duì)B樹、B+樹給出了他的意見（為了真實(shí)性，特引用其原話，未作任何改動(dòng)）：?“B+樹還有一個(gè)最大的好處，方便掃庫(kù)，B樹必須用中序遍歷的方法按序掃庫(kù)，而B+樹直接從葉子結(jié)點(diǎn)挨個(gè)掃一遍就完了，B+樹支持range-query非常方便，而B樹不支持。這是數(shù)據(jù)庫(kù)選用B+樹的最主要原因。
????比如要查 5-10之間的，B+樹一把到5這個(gè)標(biāo)記，再一把到10，然后串起來就行了，B樹就非常麻煩。B樹的好處，就是成功查詢特別有利，因?yàn)闃涞母叨瓤傮w要比B+樹矮。不成功的情況下，B樹也比B+樹稍稍占一點(diǎn)點(diǎn)便宜。
????B樹比如你的例子中查，17的話，一把就得到結(jié)果了，
有很多基于頻率的搜索是選用B樹，越頻繁query的結(jié)點(diǎn)越往根上走，前提是需要對(duì)query做統(tǒng)計(jì)，而且要對(duì)key做一些變化。
????另外B樹也好B+樹也好，根或者上面幾層因?yàn)楸环磸?fù)query，所以這幾塊基本都在內(nèi)存中，不會(huì)出現(xiàn)讀磁盤IO，一般已啟動(dòng)的時(shí)候，就會(huì)主動(dòng)換入內(nèi)存?！狈浅８兄x。
????Bucket Li："mysql 底層存儲(chǔ)是用B+樹實(shí)現(xiàn)的，知道為什么么。內(nèi)存中B+樹是沒有優(yōu)勢(shì)的，但是一到磁盤，B+樹的威力就出來了"。
?
第二節(jié)、R樹：處理空間存儲(chǔ)問題
相信經(jīng)過上面第一節(jié)的介紹，你已經(jīng)對(duì)B樹或者B+樹有所了解。這種樹可以非常好的處理一維空間存儲(chǔ)的問題。B樹是一棵平衡樹，它是把一維直線分為若干段線段，當(dāng)我們查找滿足某個(gè)要求的點(diǎn)的時(shí)候，只要去查找它所屬的線段即可。依我看來，這種思想其實(shí)就是先找一個(gè)大的空間，再逐步縮小所要查找的空間，最終在一個(gè)自己設(shè)定的最小不可分空間內(nèi)找出滿足要求的解。一個(gè)典型的B樹查找如下：
?
要查找某一滿足條件的點(diǎn)，先去找到滿足條件的線段，然后遍歷所在線段上的點(diǎn)，即可找到答案。
B樹是一種相對(duì)來說比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，尤其是在它的刪除與插入操作過程中，因?yàn)樗婕暗搅巳~子結(jié)點(diǎn)的分解與合并。由于本文第一節(jié)已經(jīng)詳細(xì)介紹了B樹和B+樹，下面直接開始介紹我們的第二個(gè)主角：R樹。
?
簡(jiǎn)介
1984年，加州大學(xué)伯克利分校的Guttman發(fā)表了一篇題為“R-trees: a dynamic index structure for spatial searching”的論文，向世人介紹了R樹這種處理高維空間存儲(chǔ)問題的數(shù)據(jù)結(jié)構(gòu)。本文便是基于這篇論文寫作完成的，因此如果大家對(duì)R樹非常有興趣，我想最好還是參考一下原著：）。為表示對(duì)這位牛人的尊重，給個(gè)引用先：
Guttman, A.; “R-trees: a dynamic index structure for spatial searching,” ACM, 1984, 14
R樹在數(shù)據(jù)庫(kù)等領(lǐng)域做出的功績(jī)是非常顯著的。它很好的解決了在高維空間搜索等問題。舉個(gè)R樹在現(xiàn)實(shí)領(lǐng)域中能夠解決的例子：查找20英里以內(nèi)所有的餐廳。如果沒有R樹你會(huì)怎么解決？一般情況下我們會(huì)把餐廳的坐標(biāo)(x,y)分為兩個(gè)字段存放在數(shù)據(jù)庫(kù)中，一個(gè)字段記錄經(jīng)度，另一個(gè)字段記錄緯度。這樣的話我們就需要遍歷所有的餐廳獲取其位置信息，然后計(jì)算是否滿足要求。如果一個(gè)地區(qū)有100家餐廳的話，我們就要進(jìn)行100次位置計(jì)算操作了，如果應(yīng)用到谷歌地圖這種超大數(shù)據(jù)庫(kù)中，這種方法便必定不可行了。
R樹就很好的解決了這種高維空間搜索問題。它把B樹的思想很好的擴(kuò)展到了多維空間，采用了B樹分割空間的思想，并在添加、刪除操作時(shí)采用合并、分解結(jié)點(diǎn)的方法，保證樹的平衡性。因此，R樹就是一棵用來存儲(chǔ)高維數(shù)據(jù)的平衡樹。
OK，接下來，本文將詳細(xì)介紹R樹的數(shù)據(jù)結(jié)構(gòu)以及R樹的操作。至于R樹的擴(kuò)展與R樹的性能問題，可以查閱相關(guān)論文。
?
R樹的數(shù)據(jù)結(jié)構(gòu)
如上所述，R樹是B樹在高維空間的擴(kuò)展，是一棵平衡樹。每個(gè)R樹的葉子結(jié)點(diǎn)包含了多個(gè)指向不同數(shù)據(jù)的指針，這些數(shù)據(jù)可以是存放在硬盤中的，也可以是存在內(nèi)存中。根據(jù)R樹的這種數(shù)據(jù)結(jié)構(gòu)，當(dāng)我們需要進(jìn)行一個(gè)高維空間查詢時(shí)，我們只需要遍歷少數(shù)幾個(gè)葉子結(jié)點(diǎn)所包含的指針，查看這些指針指向的數(shù)據(jù)是否滿足要求即可。這種方式使我們不必遍歷所有數(shù)據(jù)即可獲得答案，效率顯著提高。下圖1是R樹的一個(gè)簡(jiǎn)單實(shí)例：
我們?cè)谏厦嬲f過，R樹運(yùn)用了空間分割的理念，這種理念是如何實(shí)現(xiàn)的呢？R樹采用了一種稱為MBR(Minimal Bounding Rectangle)的方法，在此我把它譯作“最小邊界矩形”。從葉子結(jié)點(diǎn)開始用矩形（rectangle）將空間框起來，結(jié)點(diǎn)越往上，框住的空間就越大，以此對(duì)空間進(jìn)行分割。有點(diǎn)不懂？沒關(guān)系，繼續(xù)往下看。在這里我還想提一下，R樹中的R應(yīng)該代表的是Rectangle（此處參考wikipedia上關(guān)于R樹的介紹），而不是大多數(shù)國(guó)內(nèi)教材中所說的Region（很多書把R樹稱為區(qū)域樹，這是有誤的）。我們就拿二維空間來舉例。下圖是Guttman論文中的一幅圖：
?
我來詳細(xì)解釋一下這張圖。先來看圖（b）
首先我們假設(shè)所有數(shù)據(jù)都是二維空間下的點(diǎn)，圖中僅僅標(biāo)志了R8區(qū)域中的數(shù)據(jù)，也就是那個(gè)shape of data object。別把那一塊不規(guī)則圖形看成一個(gè)數(shù)據(jù)，我們把它看作是多個(gè)數(shù)據(jù)圍成的一個(gè)區(qū)域。為了實(shí)現(xiàn)R樹結(jié)構(gòu)，我們用一個(gè)最小邊界矩形恰好框住這個(gè)不規(guī)則區(qū)域，這樣，我們就構(gòu)造出了一個(gè)區(qū)域：R8。R8的特點(diǎn)很明顯，就是正正好好框住所有在此區(qū)域中的數(shù)據(jù)。其他實(shí)線包圍住的區(qū)域，如R9，R10，R12等都是同樣的道理。這樣一來，我們一共得到了12個(gè)最最基本的最小矩形。這些矩形都將被存儲(chǔ)在子結(jié)點(diǎn)中。
下一步操作就是進(jìn)行高一層次的處理。我們發(fā)現(xiàn)R8，R9，R10三個(gè)矩形距離最為靠近，因此就可以用一個(gè)更大的矩形R3恰好框住這3個(gè)矩形。
同樣道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小邊界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住這些矩形。
我想大家都應(yīng)該理解這個(gè)數(shù)據(jù)結(jié)構(gòu)的特征了。用地圖的例子來解釋，就是所有的數(shù)據(jù)都是餐廳所對(duì)應(yīng)的地點(diǎn)，先把相鄰的餐廳劃分到同一塊區(qū)域，劃分好所有餐廳之后，再把鄰近的區(qū)域劃分到更大的區(qū)域，劃分完畢后再次進(jìn)行更高層次的劃分，直到劃分到只剩下兩個(gè)最大的區(qū)域?yàn)橹?。要查找的時(shí)候就方便了。
下面就可以把這些大大小小的矩形存入我們的R樹中去了。根結(jié)點(diǎn)存放的是兩個(gè)最大的矩形，這兩個(gè)最大的矩形框住了所有的剩余的矩形，當(dāng)然也就框住了所有的數(shù)據(jù)。下一層的結(jié)點(diǎn)存放了次大的矩形，這些矩形縮小了范圍。每個(gè)葉子結(jié)點(diǎn)都是存放的最小的矩形，這些矩形中可能包含有n個(gè)數(shù)據(jù)。
在這里，讀者先不要去糾結(jié)于如何劃分?jǐn)?shù)據(jù)到最小區(qū)域矩形，也不要糾結(jié)怎樣用更大的矩形框住小矩形，這些都是下一節(jié)我們要討論的。
講完了基本的數(shù)據(jù)結(jié)構(gòu)，我們來講個(gè)實(shí)例，如何查詢特定的數(shù)據(jù)。又以餐廳為例，假設(shè)我要查詢廣州市天河區(qū)天河城附近一公里的所有餐廳地址怎么辦？
打開地圖（也就是整個(gè)R樹），先選擇國(guó)內(nèi)還是國(guó)外（也就是根結(jié)點(diǎn)）。
然后選擇華南地區(qū)（對(duì)應(yīng)第一層結(jié)點(diǎn)），選擇廣州市（對(duì)應(yīng)第二層結(jié)點(diǎn)），
再選擇天河區(qū)（對(duì)應(yīng)第三層結(jié)點(diǎn)），
最后選擇天河城所在的那個(gè)區(qū)域（對(duì)應(yīng)葉子結(jié)點(diǎn)，存放有最小矩形），遍歷所有在此區(qū)域內(nèi)的結(jié)點(diǎn)，看是否滿足我們的要求即可。
怎么樣，其實(shí)R樹的查找規(guī)則跟查地圖很像吧？對(duì)應(yīng)下圖：
一棵R樹滿足如下的性質(zhì)：
1.?????除非它是根結(jié)點(diǎn)之外，所有葉子結(jié)點(diǎn)包含有m至M個(gè)記錄索引（條目）。作為根結(jié)點(diǎn)的葉子結(jié)點(diǎn)所具有的記錄個(gè)數(shù)可以少于m。通常，m=M/2。
2.?????對(duì)于所有在葉子中存儲(chǔ)的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點(diǎn)的矩形（注意：此處所說的“矩形”是可以擴(kuò)展到高維空間的）。
3.?????每一個(gè)非葉子結(jié)點(diǎn)擁有m至M個(gè)孩子結(jié)點(diǎn)，除非它是根結(jié)點(diǎn)。
4.?????對(duì)于在非葉子結(jié)點(diǎn)上的每一個(gè)條目，i是最小的可以在空間上完全覆蓋這些條目所代表的店的矩形（同性質(zhì)2）。
5.?????所有葉子結(jié)點(diǎn)都位于同一層，因此R樹為平衡樹。
葉子結(jié)點(diǎn)的結(jié)構(gòu)
先來探究一下葉子結(jié)點(diǎn)的結(jié)構(gòu)。葉子結(jié)點(diǎn)所保存的數(shù)據(jù)形式為：(I, tuple-identifier)。
??????其中，tuple-identifier表示的是一個(gè)存放于數(shù)據(jù)庫(kù)中的tuple，也就是一條記錄，它是n維的。I是一個(gè)n維空間的矩形，并可以恰好框住這個(gè)葉子結(jié)點(diǎn)中所有記錄代表的n維空間中的點(diǎn)。I=(I0,I1,…,In-1)。其結(jié)構(gòu)如下圖所示：
下圖描述的就是在二維空間中的葉子結(jié)點(diǎn)所要存儲(chǔ)的信息。
?
在這張圖中，I所代表的就是圖中的矩形，其范圍是a<=I0<=b，c<=I1<=d。有兩個(gè)tuple-identifier，在圖中即表示為那兩個(gè)點(diǎn)。這種形式完全可以推廣到高維空間。大家簡(jiǎn)單想想三維空間中的樣子就可以了。這樣，葉子結(jié)點(diǎn)的結(jié)構(gòu)就介紹完了。
?
非葉子結(jié)點(diǎn)
??????非葉子結(jié)點(diǎn)的結(jié)構(gòu)其實(shí)與葉子結(jié)點(diǎn)非常類似。想象一下B樹就知道了，B樹的葉子結(jié)點(diǎn)存放的是真實(shí)存在的數(shù)據(jù)，而非葉子結(jié)點(diǎn)存放的是這些數(shù)據(jù)的“邊界”，或者說也算是一種索引（有疑問的讀者可以回顧一下上述第一節(jié)中講解B樹的部分）。
??????同樣道理，R樹的非葉子結(jié)點(diǎn)存放的數(shù)據(jù)結(jié)構(gòu)為：(I, child-pointer)。
??????其中，child-pointer是指向孩子結(jié)點(diǎn)的指針，I是覆蓋所有孩子結(jié)點(diǎn)對(duì)應(yīng)矩形的矩形。這邊有點(diǎn)拗口，但我想不是很難懂？給張圖：
?
D,E,F,G為孩子結(jié)點(diǎn)所對(duì)應(yīng)的矩形。A為能夠覆蓋這些矩形的更大的矩形。這個(gè)A就是這個(gè)非葉子結(jié)點(diǎn)所對(duì)應(yīng)的矩形。這時(shí)候你應(yīng)該悟到了吧？無論是葉子結(jié)點(diǎn)還是非葉子結(jié)點(diǎn)，它們都對(duì)應(yīng)著一個(gè)矩形。樹形結(jié)構(gòu)上層的結(jié)點(diǎn)所對(duì)應(yīng)的矩形能夠完全覆蓋它的孩子結(jié)點(diǎn)所對(duì)應(yīng)的矩形。根結(jié)點(diǎn)也唯一對(duì)應(yīng)一個(gè)矩形，而這個(gè)矩形是可以覆蓋所有我們擁有的數(shù)據(jù)信息在空間中代表的點(diǎn)的。
我個(gè)人感覺這張圖畫的不那么精確，應(yīng)該是矩形A要恰好覆蓋D,E,F,G，而不應(yīng)該再留出這么多沒用的空間了。但為尊重原圖的繪制者，特不作修改。
?
R樹的操作
這一部分也許是編程者最關(guān)注的問題了。這么高效的數(shù)據(jù)結(jié)構(gòu)該如何去實(shí)現(xiàn)呢？這便是這一節(jié)需要闡述的問題。
?
搜索
R樹的搜索操作很簡(jiǎn)單，跟B樹上的搜索十分相似。它返回的結(jié)果是所有符合查找信息的記錄條目。而輸入是什么？就我個(gè)人的理解，輸入不僅僅是一個(gè)范圍了，它更可以看成是一個(gè)空間中的矩形。也就是說，我們輸入的是一個(gè)搜索矩形。
先給出偽代碼：
Function：Search
描述：假設(shè)T為一棵R樹的根結(jié)點(diǎn)，查找所有搜索矩形S覆蓋的記錄條目。
S1:[查找子樹] 如果T是非葉子結(jié)點(diǎn)，如果T所對(duì)應(yīng)的矩形與S有重合，那么檢查所有T中存儲(chǔ)的條目，對(duì)于所有這些條目，使用Search操作作用在每一個(gè)條目所指向的子樹的根結(jié)點(diǎn)上（即T結(jié)點(diǎn)的孩子結(jié)點(diǎn)）。
S2:[查找葉子結(jié)點(diǎn)] 如果T是葉子結(jié)點(diǎn)，如果T所對(duì)應(yīng)的矩形與S有重合，那么直接檢查S所指向的所有記錄條目。返回符合條件的記錄。
我們通過下圖來理解這個(gè)Search操作。
?
?
陰影部分所對(duì)應(yīng)的矩形為搜索矩形。它與根結(jié)點(diǎn)對(duì)應(yīng)的最大的矩形（未畫出）有重疊。這樣將Search操作作用在其兩個(gè)子樹上。兩個(gè)子樹對(duì)應(yīng)的矩形分別為R1與R2。搜索R1，發(fā)現(xiàn)與R1中的R4矩形有重疊，繼續(xù)搜索R4。最終在R4所包含的R11與R12兩個(gè)矩形中查找是否有符合條件的記錄。搜索R2的過程同樣如此。很顯然，該算法進(jìn)行的是一個(gè)迭代操作。
?
插入
??????R樹的插入操作也同B樹的插入操作類似。當(dāng)新的數(shù)據(jù)記錄需要被添加入葉子結(jié)點(diǎn)時(shí)，若葉子結(jié)點(diǎn)溢出，那么我們需要對(duì)葉子結(jié)點(diǎn)進(jìn)行分裂操作。顯然，葉子結(jié)點(diǎn)的插入操作會(huì)比搜索操作要復(fù)雜。插入操作需要一些輔助方法才能夠完成。
來看一下偽代碼：
Function：Insert
描述：將新的記錄條目E插入給定的R樹中。
I1：[為新記錄找到合適插入的葉子結(jié)點(diǎn)] 開始ChooseLeaf方法選擇葉子結(jié)點(diǎn)L以放置記錄E。
I2：[添加新記錄至葉子結(jié)點(diǎn)] 如果L有足夠的空間來放置新的記錄條目，則向L中添加E。如果沒有足夠的空間，則進(jìn)行SplitNode方法以獲得兩個(gè)結(jié)點(diǎn)L與LL，這兩個(gè)結(jié)點(diǎn)包含了所有原來葉子結(jié)點(diǎn)L中的條目與新條目E。
I3：[將變換向上傳遞] 開始對(duì)結(jié)點(diǎn)L進(jìn)行AdjustTree操作，如果進(jìn)行了分裂操作，那么同時(shí)需要對(duì)LL進(jìn)行AdjustTree操作。
I4：[對(duì)樹進(jìn)行增高操作] 如果結(jié)點(diǎn)分裂，且該分裂向上傳播導(dǎo)致了根結(jié)點(diǎn)的分裂，那么需要?jiǎng)?chuàng)建一個(gè)新的根結(jié)點(diǎn)，并且讓它的兩個(gè)孩子結(jié)點(diǎn)分別為原來那個(gè)根結(jié)點(diǎn)分裂后的兩個(gè)結(jié)點(diǎn)。
?
Function：ChooseLeaf
描述：選擇葉子結(jié)點(diǎn)以放置新條目E。
CL1：[Initialize] 設(shè)置N為根結(jié)點(diǎn)。
CL2：[葉子結(jié)點(diǎn)的檢查] 如果N為葉子結(jié)點(diǎn)，則直接返回N。
CL3：[選擇子樹] 如果N不是葉子結(jié)點(diǎn)，則遍歷N中的結(jié)點(diǎn)，找出添加E.I時(shí)擴(kuò)張最小的結(jié)點(diǎn)，并把該結(jié)點(diǎn)定義為F。如果有多個(gè)這樣的結(jié)點(diǎn)，那么選擇面積最小的結(jié)點(diǎn)。
CL4：[下降至葉子結(jié)點(diǎn)] 將N設(shè)為F，從CL2開始重復(fù)操作。
?
Function：AdjustTree
描述：葉子結(jié)點(diǎn)的改變向上傳遞至根結(jié)點(diǎn)以改變各個(gè)矩陣。在傳遞變換的過程中可能會(huì)產(chǎn)生結(jié)點(diǎn)的分裂。
AT1：[初始化] 將N設(shè)為L(zhǎng)。
AT2：[檢驗(yàn)是否完成] 如果N為根結(jié)點(diǎn)，則停止操作。
AT3：[調(diào)整父結(jié)點(diǎn)條目的最小邊界矩形] 設(shè)P為N的父節(jié)點(diǎn)，EN為指向在父節(jié)點(diǎn)P中指向N的條目。調(diào)整EN.I以保證所有在N中的矩形都被恰好包圍。
AT4：[向上傳遞結(jié)點(diǎn)分裂] 如果N有一個(gè)剛剛被分裂產(chǎn)生的結(jié)點(diǎn)NN，則創(chuàng)建一個(gè)指向NN的條目ENN。如果P有空間來存放ENN，則將ENN添加到P中。如果沒有，則對(duì)P進(jìn)行SplitNode操作以得到P和PP。
AT5：[升高至下一級(jí)] 如果N等于L且發(fā)生了分裂，則把NN置為PP。從AT2開始重復(fù)操作。
?
同樣，我們用圖來更加直觀的理解這個(gè)插入操作。
?
?
????我們來通過圖分析一下插入操作。現(xiàn)在我們需要插入R21這個(gè)矩形。開始時(shí)我們進(jìn)行ChooseLeaf操作。在根結(jié)點(diǎn)中有兩個(gè)條目，分別為R1，R2。其實(shí)R1已經(jīng)完全覆蓋了R21，而若向R2中添加R21，則會(huì)使R2.I增大很多。顯然我們選擇R1插入。然后進(jìn)行下一級(jí)的操作。相比于R4，向R3中添加R21會(huì)更合適，因?yàn)镽3覆蓋R21所需增大的面積相對(duì)較小。這樣就在R8，R9，R10所在的葉子結(jié)點(diǎn)中插入R21。由于葉子結(jié)點(diǎn)沒有足夠空間，則要進(jìn)行分裂操作。
????插入操作如下圖所示：
?
這個(gè)插入操作其實(shí)類似于第一節(jié)中B樹的插入操作，這里不再具體介紹，不過想必看過上面的偽代碼大家應(yīng)該也清楚了。
?
刪除
R樹的刪除操作與B樹的刪除操作會(huì)有所不同，不過同B樹一樣，會(huì)涉及到壓縮等操作。相信讀者看完以下的偽代碼之后會(huì)有所體會(huì)。R樹的刪除同樣是比較復(fù)雜的，需要用到一些輔助函數(shù)來完成整個(gè)操作。
偽代碼如下：
Function：Delete
描述：將一條記錄E從指定的R樹中刪除。
D1：[找到含有記錄的葉子結(jié)點(diǎn)] 使用FindLeaf方法找到包含有記錄E的葉子結(jié)點(diǎn)L。如果搜索失敗，則直接終止。
D2：[刪除記錄] 將E從L中刪除。
D3：[傳遞記錄] 對(duì)L使用CondenseTree操作
D4：[縮減樹] 當(dāng)經(jīng)過以上調(diào)整后，如果根結(jié)點(diǎn)只包含有一個(gè)孩子結(jié)點(diǎn)，則將這個(gè)唯一的孩子結(jié)點(diǎn)設(shè)為根結(jié)點(diǎn)。
?
Function：FindLeaf
描述：根結(jié)點(diǎn)為T，期望找到包含有記錄E的葉子結(jié)點(diǎn)。
FL1：[搜索子樹] 如果T不是葉子結(jié)點(diǎn)，則檢查每一條T中的條目F，找出與E所對(duì)應(yīng)的矩形相重合的F（不必完全覆蓋）。對(duì)于所有滿足條件的F，對(duì)其指向的孩子結(jié)點(diǎn)進(jìn)行FindLeaf操作，直到尋找到E或者所有條目均以被檢查過。
FL2：[搜索葉子結(jié)點(diǎn)以找到記錄] 如果T是葉子結(jié)點(diǎn)，那么檢查每一個(gè)條目是否有E存在，如果有則返回T。
?
Function：CondenseTree
描述：L為包含有被刪除條目的葉子結(jié)點(diǎn)。如果L的條目數(shù)過少（小于要求的最小值m），則必須將該葉子結(jié)點(diǎn)L從樹中刪除。經(jīng)過這一刪除操作，L中的剩余條目必須重新插入樹中。此操作將一直重復(fù)直至到達(dá)根結(jié)點(diǎn)。同樣，調(diào)整在此修改樹的過程所經(jīng)過的路徑上的所有結(jié)點(diǎn)對(duì)應(yīng)的矩形大小。
CT1：[初始化] 令N為L(zhǎng)。初始化一個(gè)用于存儲(chǔ)被刪除結(jié)點(diǎn)包含的條目的鏈表Q。
CT2：[找到父條目] 如果N為根結(jié)點(diǎn)，那么直接跳轉(zhuǎn)至CT6。否則令P為N 的父結(jié)點(diǎn)，令EN為P結(jié)點(diǎn)中存儲(chǔ)的指向N的條目。
CT3：[刪除下溢結(jié)點(diǎn)] 如果N含有條目數(shù)少于m，則從P中刪除EN，并把結(jié)點(diǎn)N中的條目添加入鏈表Q中。
CT4：[調(diào)整覆蓋矩形] 如果N沒有被刪除，則調(diào)整EN.I使得其對(duì)應(yīng)矩形能夠恰好覆蓋N中的所有條目所對(duì)應(yīng)的矩形。
CT5：[向上一層結(jié)點(diǎn)進(jìn)行操作] 令N等于P，從CT2開始重復(fù)操作。
CT6：[重新插入孤立的條目] 所有在Q中的結(jié)點(diǎn)中的條目需要被重新插入。原來屬于葉子結(jié)點(diǎn)的條目可以使用Insert操作進(jìn)行重新插入，而那些屬于非葉子結(jié)點(diǎn)的條目必須插入刪除之前所在層的結(jié)點(diǎn)，以確保它們所指向的子樹還處于相同的層。
?
??????R樹刪除記錄過程中的CondenseTree操作是不同于B樹的。我們知道，B樹刪除過程中，如果出現(xiàn)結(jié)點(diǎn)的記錄數(shù)少于半滿（即下溢）的情況，則直接把這些記錄與其他葉子的記錄“融合”，也就是說兩個(gè)相鄰結(jié)點(diǎn)合并。然而R樹卻是直接重新插入。
?
同樣，我們用圖直觀的說明這個(gè)操作。
?
假設(shè)結(jié)點(diǎn)最大條目數(shù)為4，最小條目數(shù)為2。在這張圖中，我們的目標(biāo)是刪除記錄c。首先使用FindLeaf操作找到c所處在的葉子結(jié)點(diǎn)的位置——R11。當(dāng)c從R11刪除時(shí)，R11就只有一條記錄了，少于最小條目數(shù)2，出現(xiàn)下溢，此時(shí)要調(diào)用CondenseTree操作。這樣，c被刪除，R11剩余的條目——指向記錄d的指針——被插入鏈表Q。然后向更高一層的結(jié)點(diǎn)進(jìn)行此操作。這樣R12會(huì)被插入鏈表中。原理是一樣的，在這里就不再贅述。
有一點(diǎn)需要解釋的是，我們發(fā)現(xiàn)這個(gè)刪除操作向上傳遞之后，根結(jié)點(diǎn)的條目R1也被插入了Q中，這樣根結(jié)點(diǎn)只剩下了R2。別著急，重新插入操作會(huì)有效的解決這個(gè)問題。我們插入R3，R12，d至它原來所處的層。這樣，我們發(fā)現(xiàn)根結(jié)點(diǎn)只有一個(gè)條目了，此時(shí)根據(jù)Inert中的操作，我們把這個(gè)根結(jié)點(diǎn)刪除，它的孩子結(jié)點(diǎn)，即R5，R6，R7，R3所在的結(jié)點(diǎn)被置為根結(jié)點(diǎn)。至此，刪除操作結(jié)束。
?
結(jié)語
??????R樹是一種能夠有效進(jìn)行高維空間搜索的數(shù)據(jù)結(jié)構(gòu)，它已經(jīng)被廣泛應(yīng)用在各種數(shù)據(jù)庫(kù)及其相關(guān)的應(yīng)用中。但R樹的處理也具有局限性，它的最佳應(yīng)用范圍是處理2至6維的數(shù)據(jù)，更高維的存儲(chǔ)會(huì)變得非常復(fù)雜，這樣就不適用了。近年來，R樹也出現(xiàn)了很多變體，R*樹就是其中的一種。這些變體提升了R樹的性能，感興趣的讀者可以參考相關(guān)文獻(xiàn)。文章有任何錯(cuò)誤，還望各位讀者不吝賜教。本文完。
?
參考文獻(xiàn)以及推薦閱讀：
1.???Organization and Maintenance of Large Ordered Indices
2.???the ubiquitous B tree
3.???http://en.wikipedia.org/wiki/Btree （給出了國(guó)外一些開源地址）
4. ??http://en.wikipedia.org/wiki/Btree#Technical_description
5.???http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html（include C++ source code）
6.???http://slady.net/java/bt/view.php（如果了解了B-tree結(jié)構(gòu)，該地址可以在線對(duì)該結(jié)構(gòu)進(jìn)行查找（search），插入(insert)，刪除(delete)操作。）
7. Guttman, A.; “R-trees: a dynamic index structure for spatial searching,” ACM, 1984, 14
8. http://www.cnblogs.com/CareySon/archive/2012/04/06/2435349.html；
9.?http://baike.baidu.com/view/298408.htm。
10.?http://www.cnblogs.com/leoo2sk/archive/2011/07/10/mysql-index.html?（介紹了mysql中myisam和innodb這兩種引擎的內(nèi)部索引機(jī)制，以及對(duì)不同字段的索引時(shí)，檢索效率上的對(duì)比，主要也是基于其內(nèi)部機(jī)制的理解）
11.?http://www.oschina.net/news/31988/mysql-indexing-best-practices?（MySQL 索引最佳實(shí)踐）；
12.?http://idlebox.net/2007/stx-btree/（此頁(yè)面包含B樹生成構(gòu)造的一些演示demo）。
?
?
總結(jié)
以上是生活随笔為你收集整理的B树、B+树、B*树谈到R 树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 821是什么星座 8月21日的星座
- 下一篇： 榜的形近字