二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（Left Subtree）和“右子樹”（Right Subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。
創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),蓮池企業(yè)網(wǎng)站建設(shè),蓮池品牌網(wǎng)站建設(shè),網(wǎng)站定制,蓮池網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,蓮池網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。
二叉樹有如下特性：
每個結(jié)點都包含一個元素以及 n 個子樹，這里 0≤n≤2。?
光看概念有點枯燥，假設(shè)我們現(xiàn)在有這樣一組數(shù)[35 27 48 12 29 38 55]，順序的插入到一個數(shù)的結(jié)構(gòu)中，步驟如下 ：
好了，這就是一棵二叉樹啦！我們能看到，經(jīng)過一系列的插入操作之后，原本無序的一組數(shù)已經(jīng)變成一個有序的結(jié)構(gòu)了，并且這個樹滿足了上面提到的兩個二叉樹的特性！
但是如果同樣是上面那一組數(shù)，我們自己升序排列后再插入，也就是說按照[12 27 29 35 38 48 55]的順序插入，會怎么樣呢？
由于是升序插入，新插入的數(shù)據(jù)總是比已存在的結(jié)點數(shù)據(jù)都要大，所以每次都會往結(jié)點的右邊插入，最終導(dǎo)致這棵樹嚴(yán)重偏科！
上圖就是最壞的情況，也就是一棵樹退化為一個線性鏈表了，這樣查找效率自然就低了，完全沒有發(fā)揮樹的優(yōu)勢了呢！?
為了較大發(fā)揮二叉樹的查找效率，讓二叉樹不再偏科，保持各科平衡，所以有了平衡二叉樹！
平衡二叉樹是一種特殊的二叉樹，所以他也滿足前面說到的二叉樹的兩個特性，同時還有一個特性：它的左右兩個子樹的高度差的絕對值不超過 1，并且左右兩個子樹都是一棵平衡二叉樹。
大家也看到了前面[35 27 48 12 29 38 55]插入完成后的圖，其實就已經(jīng)是一棵平衡二叉樹啦。
那如果按照[12 27 29 35 38 48 55]的順序插入一棵平衡二叉樹，會怎么樣呢？
我們看看插入以及平衡的過程：
這棵樹始終滿足平衡二叉樹的幾個特性而保持平衡！這樣我們的樹也不會退化為線性鏈表了！
我們需要查找一個數(shù)的時候就能沿著樹根一直往下找，這樣的查找效率和二分法查找是一樣的呢！
一棵平衡二叉樹能容納多少的結(jié)點呢？這跟樹的高度是有關(guān)系的，假設(shè)樹的高度為 h，那每一層最多容納的結(jié)點數(shù)量為 2^(n-1)，整棵樹最多容納節(jié)點數(shù)為 2^0+2^1+2^2+...+2^(h-1)。
這樣計算，100w 數(shù)據(jù)樹的高度大概在 20 左右，也就是說從有著 100w 條數(shù)據(jù)的平衡二叉樹中找一個數(shù)據(jù)，最壞的情況下需要 20 次查找。
如果是內(nèi)存操作，效率也是很高的！但是我們數(shù)據(jù)庫中的數(shù)據(jù)基本都是放在磁盤中的，每讀取一個二叉樹的結(jié)點就是一次磁盤 IO，這樣我們找一條數(shù)據(jù)如果要經(jīng)過 20?次磁盤的 IO？
那性能就成了一個很大的問題了！那我們是不是可以把這棵樹壓縮一下，讓每一層能夠容納更多的節(jié)點呢？雖然我矮，但是我胖啊...
這顆矮胖的樹就是 B-Tree，注意中間是杠精的杠而不是減，所以也不要讀成 B 減 Tree 了~
那 B-Tree 有哪些特性呢？一棵 m 階的 B-Tree 有如下特性：
每個結(jié)點最多 m 個子結(jié)點。?
除了根結(jié)點和葉子結(jié)點外，每個結(jié)點最少有 m/2（向上取整）個子結(jié)點。?
如果根結(jié)點不是葉子結(jié)點，那根結(jié)點至少包含兩個子結(jié)點。?
所有的葉子結(jié)點都位于同一層。?
每個結(jié)點都包含 k 個元素（關(guān)鍵字），這里 m/2≤k。
每個節(jié)點中的元素（關(guān)鍵字）從小到大排列。?
是不是感覺跟丈母娘張口問你要彩禮一樣，列一堆的條件，而且每一條都讓你很懵逼！
下面我們以一個[0,1,2,3,4,5,6,7]的數(shù)組插入一棵 3 階的 B-Tree 為例，將所有的條件都串起來，你就明白了！
那么，你是否對 B-Tree 的幾點特性都清晰了呢？在二叉樹中，每個結(jié)點只有一個元素。
但是在 B-Tree 中，每個結(jié)點都可能包含多個元素，并且非葉子結(jié)點在元素的左右都有指向子結(jié)點的指針。
如果需要查找一個元素，那流程是怎么樣的呢？我們看下圖，如果我們要在下面的 B-Tree 中找到關(guān)鍵字 24，那流程如下：
從這個流程我們能看出，B-Tree 的查詢效率好像也并不比平衡二叉樹高。但是查詢所經(jīng)過的結(jié)點數(shù)量要少很多，也就意味著要少很多次的磁盤 IO，這對性能的提升是很大的。
從前面對 B-Tree 操作的圖，我們能看出來，元素就是類似 1、2、3 這樣的數(shù)值。
但是數(shù)據(jù)庫的數(shù)據(jù)都是一條條的數(shù)據(jù)，如果某個數(shù)據(jù)庫以 B-Tree 的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，那數(shù)據(jù)怎么存放的呢？
我們看下一張圖：
普通的 B-Tree 的結(jié)點中，元素就是一個個的數(shù)字。但是上圖中，我們把元素部分拆分成了 key-data 的形式，Key 就是數(shù)據(jù)的主鍵，Data 就是具體的數(shù)據(jù)。
這樣我們在找一條數(shù)的時候，就沿著根結(jié)點往下找就 OK 了，效率是比較高的。
B+Tree 是在 B-Tree 基礎(chǔ)上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結(jié)構(gòu)。
B+Tree 與 B-Tree 的結(jié)構(gòu)很像，但是也有幾個自己的特性：
所有的非葉子節(jié)點只存儲關(guān)鍵字信息。?
所有衛(wèi)星數(shù)據(jù)（具體數(shù)據(jù)）都存在葉子結(jié)點中。?
所有的葉子結(jié)點中包含了全部元素的信息。?
如果上面 B-Tree 的圖變成 B+Tree，那應(yīng)該如下：?
大家仔細(xì)對比于 B-Tree 的圖能發(fā)現(xiàn)什么不同？
非葉子結(jié)點上已經(jīng)只有 Key 信息了，滿足上面第 1 點特性！?
所有葉子結(jié)點下面都有一個 Data 區(qū)域，滿足上面第 2 點特性！?
非葉子結(jié)點的數(shù)據(jù)在葉子結(jié)點上都能找到，如根結(jié)點的元素 4、8 在最底層的葉子結(jié)點上也能找到，滿足上面第 3 點特性！?
在講這兩種數(shù)據(jù)結(jié)構(gòu)在數(shù)據(jù)庫中的選擇之前，我們還需要了解的一個知識點是操作系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存是以磁盤塊（Block）為基本單位的，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來，而不是需要什么取什么。
即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。
這樣做的理論依據(jù)是計算機科學(xué)中著名的局部性原理：當(dāng)一個數(shù)據(jù)被用到時，其附近的數(shù)據(jù)也通常會馬上被使用。?
預(yù)讀的長度一般為頁（Page）的整倍數(shù)。頁是計算機管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統(tǒng)中，頁的大小通常為 4K）。
B-Tree 和 B+Tree 該如何選擇呢？都有哪些優(yōu)劣呢？
①B-Tree 因為非葉子結(jié)點也保存具體數(shù)據(jù)，所以在查找某個關(guān)鍵字的時候找到即可返回。
而 B+Tree 所有的數(shù)據(jù)都在葉子結(jié)點，每次查找都得到葉子結(jié)點。所以在同樣高度的 B-Tree 和 B+Tree 中，B-Tree 查找某個關(guān)鍵字的效率更高。?
②由于 B+Tree 所有的數(shù)據(jù)都在葉子結(jié)點，并且結(jié)點之間有指針連接，在找大于某個關(guān)鍵字或者小于某個關(guān)鍵字的數(shù)據(jù)的時候，B+Tree 只需要找到該關(guān)鍵字然后沿著鏈表遍歷就可以了，而 B-Tree 還需要遍歷該關(guān)鍵字結(jié)點的根結(jié)點去搜索。?
③由于 B-Tree 的每個結(jié)點（這里的結(jié)點可以理解為一個數(shù)據(jù)頁）都存儲主鍵+實際數(shù)據(jù)，而 B+Tree 非葉子結(jié)點只存儲關(guān)鍵字信息，而每個頁的大小是有限的，所以同一頁能存儲的 B-Tree 的數(shù)據(jù)會比 B+Tree 存儲的更少。
這樣同樣總量的數(shù)據(jù)，B-Tree 的深度會更大，增大查詢時的磁盤 I/O 次數(shù)，進(jìn)而影響查詢效率。?
鑒于以上的比較，所以在常用的關(guān)系型數(shù)據(jù)庫中，都是選擇 B+Tree 的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)！
下面我們以 MySQL 的 InnoDB 存儲引擎為例講解，其他類似 SQL Server、Oracle 的原理！
在 InnoDB 存儲引擎中，也有頁的概念，默認(rèn)每個頁的大小為 16K，也就是每次讀取數(shù)據(jù)時都是讀取 4*4K 的大??！
假設(shè)我們現(xiàn)在有一個用戶表，我們往里面寫數(shù)據(jù)：
這里需要注意的一點是，在某個頁內(nèi)插入新行時，為了減少數(shù)據(jù)的移動，通常是插入到當(dāng)前行的后面或者是已刪除行留下來的空間，所以在某一個頁內(nèi)的數(shù)據(jù)并不是完全有序的（后面頁結(jié)構(gòu)部分有細(xì)講）。
但是為了數(shù)據(jù)訪問順序性，在每個記錄中都有一個指向下一條記錄的指針，以此構(gòu)成了一條單向有序鏈表，不過在這里為了方便演示我是按順序排列的！
由于數(shù)據(jù)還比較少，一個頁就能容下，所以只有一個根結(jié)點，主鍵和數(shù)據(jù)也都是保存在根結(jié)點（左邊的數(shù)字代表主鍵，右邊名字、性別代表具體的數(shù)據(jù)）。
假設(shè)我們寫入 10 條數(shù)據(jù)之后，Page1 滿了，再寫入新的數(shù)據(jù)會怎么存放呢？
我們繼續(xù)看下圖：
有個叫“秦壽生”的朋友來了，但是 Page1 已經(jīng)放不下數(shù)據(jù)了，這時候就需要進(jìn)行頁分裂，產(chǎn)生一個新的 Page。
在 InnoDB 中的流程是怎么樣的呢？
產(chǎn)生新的 Page2，然后將 Page1 的內(nèi)容復(fù)制到 Page2。?
產(chǎn)生新的 Page3，“秦壽生”的數(shù)據(jù)放入 Page3。?
這里有兩個問題需要注意的是：
①為什么要復(fù)制 Page1 為 Page2 而不是創(chuàng)建一個新的頁作為根結(jié)點，這樣就少了一步復(fù)制的開銷了？
如果是重新創(chuàng)建根結(jié)點，那根結(jié)點存儲的物理地址可能經(jīng)常會變，不利于查找。
并且在 InnoDB 中根結(jié)點是會預(yù)讀到內(nèi)存中的，所以結(jié)點的物理地址固定會比較好！
②原來 Page1 有 10?條數(shù)據(jù)，在插入第 11 條數(shù)據(jù)的時候進(jìn)行裂變，根據(jù)前面對 B-Tree、B+Tree 特性的了解，那這至少是一棵 11 階的樹，裂變之后每個結(jié)點的元素至少為 11/2=5 個。
那是不是應(yīng)該頁裂變之后主鍵 1-5 的數(shù)據(jù)還是在原來的頁，主鍵 6-11 的數(shù)據(jù)會放到新的頁，根結(jié)點存放主鍵 6？?
如果是這樣的話，新的頁空間利用率只有 50%，并且會導(dǎo)致更為頻繁的頁分裂。
所以 InnoDB 對這一點做了優(yōu)化，新的數(shù)據(jù)放入新創(chuàng)建的頁，不移動原有頁面的任何記錄。
隨著數(shù)據(jù)的不斷寫入，這棵樹也逐漸枝繁葉茂，如下圖：
每次新增數(shù)據(jù)，都是將一個頁寫滿，然后新創(chuàng)建一個頁繼續(xù)寫，這里其實是有個隱含條件的，那就是主鍵自增！
主鍵自增寫入時新插入的數(shù)據(jù)不會影響到原有頁，插入效率高！且頁的利用率高！
但是如果主鍵是無序的或者隨機的，那每次的插入可能會導(dǎo)致原有頁頻繁的分裂，影響插入效率！降低頁的利用率！這也是為什么在 InnoDB 中建議設(shè)置主鍵自增的原因！
這棵樹的非葉子結(jié)點上存的都是主鍵，那如果一個表沒有主鍵會怎么樣？在 InnoDB 中，如果一個表沒有主鍵，那默認(rèn)會找建了唯一索引的列，如果也沒有，則會生成一個隱形的字段作為主鍵！
有數(shù)據(jù)插入那就有刪除，如果這個用戶表頻繁的插入和刪除，那會導(dǎo)致數(shù)據(jù)頁產(chǎn)生碎片，頁的空間利用率低，還會導(dǎo)致樹變的“虛高”，降低查詢效率！這可以通過索引重建來消除碎片提高查詢效率！
數(shù)據(jù)插入了怎么查找呢？
找到數(shù)據(jù)所在的頁。這個查找過程就跟前面說到的 B+Tree 的搜索過程是一樣的，從根結(jié)點開始查找一直到葉子結(jié)點。?
這跟我們在新華字典中找某個漢字是一樣的，先通過字典的索引定位到該漢字拼音所在的頁，然后到指定的頁找到具體的漢字。
InnoDB 中定位到頁后用了哪種策略快速查找某個主鍵呢？這我們就需要從頁結(jié)構(gòu)開始了解。
左邊藍(lán)色區(qū)域稱為 Page Directory，這塊區(qū)域由多個 Slot 組成，是一個稀疏索引結(jié)構(gòu)，即一個槽中可能屬于多個記錄，最少屬于 4 條記錄，最多屬于 8 條記錄。
槽內(nèi)的數(shù)據(jù)是有序存放的，所以當(dāng)我們尋找一條數(shù)據(jù)的時候可以先在槽中通過二分法查找到一個大致的位置。
右邊區(qū)域為數(shù)據(jù)區(qū)域，每一個數(shù)據(jù)頁中都包含多條行數(shù)據(jù)。注意看圖中最上面和最下面的兩條特殊的行記錄 Infimum 和 Supremum，這是兩個虛擬的行記錄。
在沒有其他用戶數(shù)據(jù)的時候 Infimum 的下一條記錄的指針指向 Supremum。
當(dāng)有用戶數(shù)據(jù)的時候，Infimum 的下一條記錄的指針指向當(dāng)前頁中最小的用戶記錄，當(dāng)前頁中最大的用戶記錄的下一條記錄的指針指向 Supremum，至此整個頁內(nèi)的所有行記錄形成一個單向鏈表。
行記錄被 Page Directory 邏輯的分成了多個塊，塊與塊之間是有序的，也就是說“4”這個槽指向的數(shù)據(jù)塊內(nèi)最大的行記錄的主鍵都要比“8”這個槽指向的數(shù)據(jù)塊內(nèi)最小的行記錄的主鍵要小。但是塊內(nèi)部的行記錄不一定有序。
每個行記錄的都有一個 n_owned 的區(qū)域（圖中粉紅色區(qū)域），n_owned 標(biāo)識這個塊有多少條數(shù)據(jù)。
偽記錄 Infimum 的 n_owned 值總是 1，記錄 Supremum 的 n_owned 的取值范圍為[1,8]，其他用戶記錄 n_owned 的取值范圍[4,8]。
并且只有每個塊中最大的那條記錄的 n_owned 才會有值，其他的用戶記錄的 n_owned 為 0。
所以當(dāng)我們要找主鍵為 6 的記錄時，先通過二分法在稀疏索引中找到對應(yīng)的槽，也就是 Page Directory 中“8”這個槽。
“8”這個槽指向的是該數(shù)據(jù)塊中最大的記錄，而數(shù)據(jù)是單向鏈表結(jié)構(gòu)，所以無法逆向查找。
所以需要找到上一個槽即“4”這個槽，然后通過“4”這個槽中最大的用戶記錄的指針沿著鏈表順序查找到目標(biāo)記錄。
前面關(guān)于數(shù)據(jù)存儲的都是演示的聚集索引的實現(xiàn)，如果上面的用戶表需要以“用戶名字”建立一個非聚集索引，是怎么實現(xiàn)的呢？
我們看下圖：
非聚集索引的存儲結(jié)構(gòu)與前面是一樣的，不同的是在葉子結(jié)點的數(shù)據(jù)部分存的不再是具體的數(shù)據(jù)，而是數(shù)據(jù)的聚集索引的 Key。
所以通過非聚集索引查找的過程是先找到該索引 Key 對應(yīng)的聚集索引的 Key，然后再拿聚集索引的 Key 到主鍵索引樹上查找對應(yīng)的數(shù)據(jù)，這個過程稱為回表！
PS：圖中的這些名字均來源于網(wǎng)絡(luò)，希望沒有誤傷正在看這篇文章的你~^_^
上面包括存儲和搜索都是拿的 InnoDB 引擎為例，那 MyISAM 與 InnoDB 在存儲上有啥不同呢？憋縮話，看圖：
上圖為 MyISAM 主鍵索引的存儲結(jié)構(gòu)，我們能看到的不同是：
主鍵索引樹的葉子結(jié)點的數(shù)據(jù)區(qū)域沒有存放實際的數(shù)據(jù)，存放的是數(shù)據(jù)記錄的地址。?
也就是說 InnoDB 引擎數(shù)據(jù)在物理上是按主鍵順序存放，而 MyISAM 引擎數(shù)據(jù)在物理上按插入的順序存放。
并且 MyISAM 的葉子結(jié)點不存放數(shù)據(jù)，所以非聚集索引的存儲結(jié)構(gòu)與聚集索引類似，在使用非聚集索引查找數(shù)據(jù)的時候通過非聚集索引樹就能直接找到數(shù)據(jù)的地址了，不需要回表，這比 InnoDB 的搜索效率會更高呢！
大家經(jīng)常會在很多的文章或書中能看到一些索引的使用建議，比如說：
like 的模糊查詢以 % 開頭，會導(dǎo)致索引失效。?
一個表建的索引盡量不要超過 5 個。?
盡量使用覆蓋索引。?
盡量不要在重復(fù)數(shù)據(jù)多的列上建索引。?
很多這里就不一一列舉了！那看完這篇文章，我們能否帶著疑問去分析一下為什么要有這些建議？
為什么 like 的模糊查詢以 % 開頭，會導(dǎo)致索引失效？為什么一個表建的索引盡量不要超過 5 個？
為什么？為什么？？為什么？？？相信看到這里的你再加上自己的一些思考應(yīng)該有答案了吧？
重慶分公司
重慶分公司
