從b 樹、b+ 樹、b* 樹到r 樹
作者：july、weedge、frankie。程式設計藝術室出品。
說明：本文從b樹開始談起，然後論述b+樹、b*樹，最後談到r 樹。其中b樹、b+樹及b*樹部分由weedge完成，r 樹部分由frankie完成，全文最終由july統稿修訂完成。
出處： 。
第一節、b樹、b+樹、b*樹
1.前言：
動態查詢樹主要有：二叉查詢樹（binary search tree），平衡二叉查詢樹（balanced binary search tree），紅黑樹(red-black tree )，b-tree/b+-tree/ b*-tree (b~tree)。前三者是典型的二叉查詢樹結構，其查詢的時間複雜度o(log2n)與樹的深度相關，那麼降低樹的深度自然會提高查詢效率。
但是咱們有面對這樣乙個實際問題：就是大規模資料儲存中，實現索引查詢這樣乙個實際背景下，樹節點儲存的元素數量是有限的（如果元素數量非常多的話，查詢就退化成節點內部的線性查詢了），這樣導致二叉查詢樹結構由於樹的深度過大而造成磁碟i/o讀寫過於頻繁，進而導致查詢效率低下（為什麼會出現這種情況，待會在外部儲存器-磁碟中有所解釋），那麼如何減少樹的深度（當然是不能減少查詢的資料量），乙個基本的想法就是：採用多叉樹結構（由於樹節點元素數量是有限的，自然該節點的子樹數量也就是有限的）。
這樣我們就提出了乙個新的查詢樹結構——多路查詢樹。根據平衡二叉樹的啟發，自然就想到平衡多路查詢樹結構，也就是這篇文章所要闡述的第乙個主題b-tree(b樹結構)。b-tree（b-tree樹即b樹）這棵神奇的樹是在rudolf bayer, edward m.
mccreight(1970)寫的一篇**《organization and maintenance of large ordered indices》中首次提出的（wikipedia中：闡述了b-tree名字**以及相關的開源位址）。在開始介紹b-tree之前，先了解下相關的硬體知識，才能很好的了解為什麼需要b-tree這種外存資料結構。
2.外儲存器—磁碟
計算機儲存裝置一般分為兩種：記憶體儲器(main memory)和外儲存器(external memory)。 記憶體訪問速度快，但容量小，**昂貴，而且不能長期儲存資料(在不通電情況下資料會消失)。
外儲存器—磁碟是一種直接訪問的儲存裝置(dasd)。它是以訪問時間變化不大為特徵的。可以直接訪問任何字元組，且容量大、速度較其它外存裝置更快。
2.1磁碟的構造
磁碟是乙個扁平的圓盤(與電唱機的唱片類似)。盤面上有許多稱為磁軌的圓圈，資料就記錄在這些磁軌上。磁碟可以是單片的，也可以是由若干碟片組成的盤組，每一盤片上有兩個面。
如下圖11.3中所示的6片盤組為例，除去最頂端和最底端的外側面不儲存資料之外，一共有10個面可以用來儲存資訊。
當磁碟驅動器執行讀/寫功能時。碟片裝在乙個主軸上，並繞主軸高速旋轉，當磁軌在讀/寫頭(又叫磁頭) 下通過時，就可以進行資料的讀 / 寫了。
一般磁碟分為固定頭盤(磁頭固定)和活動頭盤。固定頭盤的每乙個磁軌上都有獨立的磁頭，它是固定不動的，專門負責這一磁軌上資料的讀/寫。
活動頭盤 (如上圖)的磁頭是可移動的。每乙個盤面上只有乙個磁頭(磁頭是雙向的，因此正反盤面都能讀寫)。它可以從該面的乙個磁軌移動到另乙個磁軌。
所有磁頭都裝在同乙個動臂上，因此不同盤面上的所有磁頭都是同時移動的(行動整齊劃一)。當碟片繞主軸旋轉的時候，磁頭與旋轉的碟片形成乙個圓柱體。各個盤面上半徑相同的磁軌組成了乙個圓柱面，我們稱為柱面 。
因此，柱面的個數也就是盤面上的磁軌數。
2.2磁碟的讀/寫原理和效率
磁碟上資料必須用乙個三維位址唯一標示：柱面號、盤面號、塊號(磁軌上的盤塊)。
讀/寫磁碟上某一指定資料需要下面3個步驟：
(1)首先移動臂根據柱面號使磁頭移動到所需要的柱面上，這一過程被稱為定位或查詢 。
(2)如上圖11.3中所示的6盤組示意圖中，所有磁頭都定位到了10個盤面的10條磁軌上(磁頭都是雙向的)。這時根據盤面號來確定指定盤面上的磁軌。
(3)盤面確定以後，碟片開始旋轉，將指定塊號的磁軌段移動至磁頭下。
經過上面三個步驟，指定資料的儲存位置就被找到。這時就可以開始讀/寫操作了。
訪問某一具體資訊，由3部分時間組成：
●查詢時間(seek time) ts: 完成上述步驟(1)所需要的時間。這部分時間代價最高，最大可達到0.1s左右。
●等待時間(latency time) tl: 完成上述步驟(3)所需要的時間。由於碟片繞主軸旋轉速度很快，一般為7200轉/分(電腦硬碟的效能指標之一, 家用的普通硬碟的轉速一般有5400rpm(筆記本)、7200rpm幾種)。
因此一般旋轉一圈大約0.0083s。
●傳輸時間(transmission time) tt: 資料通過系統匯流排傳送到記憶體的時間，一般傳輸乙個位元組(byte)大概0.02us=2*10^(-8)s
磁碟讀取資料是以盤塊(block)為基本單位的。位於同一盤塊中的所有資料都能被一次性全部讀取出來。而磁碟io代價主要花費在查詢時間ts上。
因此我們應該盡量將相關資訊存放在同一盤塊，同一磁軌中。或者至少放在同一柱面或相鄰柱面上，以求在讀/寫資訊時儘量減少磁頭來回移動的次數，避免過多的查詢時間ts。
所以，在大規模資料儲存方面，大量資料儲存在外存磁碟中，而在外存磁碟中讀取/寫入塊(block)中某資料時，首先需要定位到磁碟中的某塊，如何有效地查詢磁碟中的資料，需要一種合理高效的外存資料結構，就是下面所要重點闡述的b-tree結構，以及相關的變種結構：b+-tree結構和b*-tree結構。
樹 具體講解之前，有一點，再次強調下：b-樹，即為b樹。因為b樹的原英文名稱為b-tree，而國內很多人喜歡把b-tree譯作b-樹，其實，這是個非常不好的直譯，很容易讓人產生誤解。
如人們可能會以為b-樹是一種樹，而b樹又是一種一種樹。而事實上是，b-tree就是指的b樹。特此說明。
我們知道，b 樹是為了磁碟或其它儲存裝置而設計的一種多叉（下面你會看到，相對於二叉，b樹每個內結點有多個分支，即多叉）平衡查詢樹。與本blog之前介紹的紅黑樹很相似，但在降低磁碟i/0操作方面要更好一些。許多資料庫系統都一般使用b樹或者b樹的各種變形結構，如下文即將要介紹的b+樹，b*樹來儲存資訊。
b樹與紅黑樹最大的不同在於，b樹的結點可以有許多子女，從幾個到幾千個。那為什麼又說b樹與紅黑樹很相似呢?因為與紅黑樹一樣，一棵含n個結點的b樹的高度也為o（lgn），但可能比一棵紅黑樹的高度小許多，應為它的分支因子比較大。
所以，b樹可以在o（logn）時間內，實現各種如插入（insert），刪除（delete）等動態集合操作。
如下圖所示，即是一棵b樹，一棵關鍵字為英語中子音字母的b樹，現在要從樹種查詢字母r（包含n[x]個關鍵字的內結點x，x有n[x]+1]個子女（也就是說，乙個內結點x若含有n[x]個關鍵字，那麼x將含有n[x]+1個子女）。所有的葉結點都處於相同的深度，帶陰影的結點為查詢字母r時要檢查的結點）：
相信，從上圖你能輕易的看到，乙個內結點x若含有n[x]個關鍵字，那麼x將含有n[x]+1個子女。如含有2個關鍵字d h的內結點有3個子女，而含有3個關鍵字q t x的內結點有4個子女。
b 樹又叫平衡多路查詢樹。一棵m階的b 樹 (m叉樹)的特性如下：
樹中每個結點最多含有m個孩子（m>=2）；
除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子（其中ceil(x)是乙個取上限的函式）；
若根結點不是葉子結點，則至少有2個孩子（特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有乙個根節點）；
所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字資訊(可以看做是外部接點或查詢失敗的接點，實際上這些結點不存在，指向這些結點的指標都為null)；
每個非終端結點中包含有n個關鍵字資訊： (n，p0，k1，p1，k2，p2，......，kn，pn)。其中：
a) ki (i=1...n)為關鍵字，且關鍵字按順序公升序排序k(i-1)< ki。
b) pi為指向子樹根的接點，且指標p(i-1)指向子樹種所有結點的關鍵字均小於ki，但都大於k(i-1)。
c) 關鍵字的個數n必須滿足： [ceil(m / 2)-1]<= n <= m-1。
針對上面第5點，再闡述下：b樹中每乙個結點能包含的關鍵字（如之前上面的d h和q t x）數有乙個上界和下界。這兩個界可以用乙個稱作b樹的最小度數（演算法導論中文版上譯作度數）t（t>=2）表示。
每個非根的結點必須至少含有t-1個關鍵字。每個非根的內結點至少有t個子女。如果樹是非空的，則根結點至少包含乙個關鍵字；
每個結點可包含之多2t-1個關鍵字。所以乙個內結點至多可有2t個子女。如果乙個結點恰好有2t-1個關鍵字，我們就說這個結點是滿的（而稍後介紹的b*樹作為b樹的一種常用變形，b*樹中要求每個內結點至少為2/3滿，而不是像這裡的b樹所要求的至少半滿）；
當關鍵字數t=2（t=2的意思是，tmin=2，t可以》=2）時的b樹是最簡單的（有很多人會因此誤認為b樹就是二叉查詢樹，但二叉查詢樹就是二叉查詢樹，b樹就是b樹，b樹的真正最準確的定義為：一棵含有t（t>=2）個關鍵字的平衡多路查詢樹）。每個內結點可能因此而含有2個、3個或4個子女，亦即一棵2-3-4樹，然而在實際中，通常採用大得多的t值。
b樹中的每個結點根據實際情況可以包含大量的關鍵字資訊和分支(當然是不能超過磁碟塊的大小，根據磁碟驅動(disk drives)的不同，一般塊的大小在1k~4k左右)；這樣樹的深度降低了，這就意味著查詢乙個元素只要很少結點從外存磁碟中讀入記憶體，很快訪問到要查詢的資料。
為了簡單，這裡用少量資料構造一棵3叉樹的形式，實際應用中的b樹結點中關鍵字很多的。上面的圖中比如根結點，其中17表示乙個磁碟檔案的檔名；小紅方塊表示這個17檔案的內容在硬碟中的儲存位置；p1表示指向17左子樹的指標。
實驗四哈夫曼樹及其的應用
一 實驗目的 1 在二叉樹基本操作的基礎上，掌握對二叉樹的一些其它操作的具體現方法.2.掌握構造哈夫曼樹以及哈夫曼編碼的方法.3 熟練掌握哈夫曼樹 最優二叉樹 特徵及其應用.二 實驗內容 哈夫曼樹和哈夫曼編碼 從終端輸入若干個字元，統計 或指定 字元出現的頻率，將字元出現的頻率作為結點的權值，建立哈...
事件樹法原理及其在堤壩風險分析中的應用
解家畢孫東亞 中國水利水電科學研究院，北京，100044 摘要 提出了事件樹構建的原理和方法 及分枝概率的計算方法，事件樹法能靈活地處理自然變化及認識不確定性等因素引起的系統反應，其在堤壩風險分析中應用較廣。以乙個例項介紹了其在堤防風險分析中的應用，例項考慮了堤防的三種可能破壞模式 漫頂 結構失穩 ...
建築變形測量的等級及其精度要求
2.0.6 對乙個實際工程，變形測量的精度等級應先根據各類建 構 築物的變形允許值按本規程第3 4章的規定進行估算，然後按以下原則確定 當僅給定單一變形允許值時，應按所估算的觀測點精度選擇相應的精度等級 當給定多個同型別變形允許值時，應分別估算觀測點精度，並應根據其中最高精度選擇相應的精度等級 當估...