BTree和B+Tree詳解

• 二叉查找樹
• 平衡二叉樹（AVL Tree）
• B-Tree（平衡多路查找樹）
• B+Tree
• B+Tree和B-Tree的區(qū)別
• 聚集索引和非聚集索引區(qū)別?
• 為什么說B+比B樹更適合實際應用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引苏遥？

最近想重新復習數(shù)據(jù)結構的知識朝墩，想了解B樹和B+樹的區(qū)別，看了挺多篇博文的戴尸，但看了還是懵懵的粥航，看不懂二叉樹和B+樹的圖琅捏。。递雀。果然有心人總能找到想要的柄延，以下是一位大神寫的BTree和B+Tree詳解，我轉載過來和大家分享

B+樹索引是B+樹在數(shù)據(jù)庫中的一種實現(xiàn)缀程，是最常見也是數(shù)據(jù)庫中使用最為頻繁的一種索引搜吧。B+樹中的B代表平衡(balance)，而不是二叉(binary)杨凑，因為B+樹是從最早的平衡二叉樹演化而來的滤奈。在講B+樹之前必須先了解二叉查找樹、平衡二叉樹(AVLTree)和平衡多路查找樹(B-Tree)撩满，B+樹即由這些樹逐步優(yōu)化而來蜒程。

二叉查找樹

二叉樹的性質
二叉樹具有以下性質：左子樹的鍵值小于根的鍵值绅你，右子樹的鍵值大于根的鍵值。
如下圖所示就是一棵二叉查找樹搞糕，

二叉查找樹

對該二叉樹的節(jié)點進行查找發(fā)現(xiàn)深度為1的節(jié)點的查找次數(shù)為1勇吊，深度為2的查找次數(shù)為2，深度為n的節(jié)點的查找次數(shù)為n窍仰，因此其平均查找次數(shù)為 (1+2+2+3+3+3) / 6 = 2.3次

二叉查找樹可以任意地構造汉规，同樣是2,3,5,6,7,8這六個數(shù)字，也可以按照下圖的方式來構造：

在這里插入圖片描述

但是這棵二叉樹的查詢效率就低了驹吮。因此若想二叉樹的查詢效率盡可能高针史，需要這棵二叉樹是平衡的，從而引出新的定義——平衡二叉樹碟狞，或稱AVL樹啄枕。

平衡二叉樹（AVL Tree）

平衡二叉樹（AVL樹）是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹族沃。也就是說在符合二叉查找樹的條件下频祝，它還滿足任何節(jié)點的兩個子樹的高度最大差為1。
下面的兩張圖片脆淹，左邊是AVL樹常空，它的任何節(jié)點的兩個子樹的高度差<=1；右邊的不是AVL樹盖溺，其根節(jié)點的左子樹高度為3漓糙，而右子樹高度為1；

平衡二叉樹

如果在AVL樹中進行插入或刪除節(jié)點烘嘱，可能導致AVL樹失去平衡昆禽，這種失去平衡的二叉樹可以概括為四種姿態(tài)：LL（左左）、RR（右右）蝇庭、LR（左右）醉鳖、RL（右左）。它們的示意圖如下：

在這里插入圖片描述

這四種失去平衡的姿態(tài)都有各自的定義：
LL：LeftLeft哮内，也稱“左左”辐棒。插入或刪除一個節(jié)點后，根節(jié)點的左孩子（Left Child）的左孩子（Left Child）還有非空節(jié)點牍蜂，導致根節(jié)點的左子樹高度比右子樹高度高2，AVL樹失去平衡泰涂。

RR：RightRight鲫竞，也稱“右右”。插入或刪除一個節(jié)點后逼蒙，根節(jié)點的右孩子（Right Child）的右孩子（Right Child）還有非空節(jié)點从绘，導致根節(jié)點的右子樹高度比左子樹高度高2，AVL樹失去平衡。

LR：LeftRight僵井，也稱“左右”陕截。插入或刪除一個節(jié)點后，根節(jié)點的左孩子（Left Child）的右孩子（Right Child）還有非空節(jié)點批什，導致根節(jié)點的左子樹高度比右子樹高度高2农曲，AVL樹失去平衡。

RL：RightLeft驻债，也稱“右左”乳规。插入或刪除一個節(jié)點后，根節(jié)點的右孩子（Right Child）的左孩子（Left Child）還有非空節(jié)點合呐，導致根節(jié)點的右子樹高度比左子樹高度高2暮的，AVL樹失去平衡。

AVL樹失去平衡之后淌实，可以通過旋轉使其恢復平衡冻辩。下面分別介紹四種失去平衡的情況下對應的旋轉方法。

LL的旋轉拆祈。LL失去平衡的情況下恨闪，可以通過一次旋轉讓AVL樹恢復平衡。步驟如下：

1. 將根節(jié)點的左孩子作為新根節(jié)點缘屹。
2. 將新根節(jié)點的右孩子作為原根節(jié)點的左孩子凛剥。
3. 將原根節(jié)點作為新根節(jié)點的右孩子。

LL旋轉示意圖如下：

在這里插入圖片描述

RR的旋轉：RR失去平衡的情況下轻姿，旋轉方法與LL旋轉對稱犁珠，步驟如下：

1. 將根節(jié)點的右孩子作為新根節(jié)點。
2. 將新根節(jié)點的左孩子作為原根節(jié)點的右孩子互亮。
3. 將原根節(jié)點作為新根節(jié)點的左孩子犁享。

RR旋轉示意圖如下：

在這里插入圖片描述

LR的旋轉：LR失去平衡的情況下，需要進行兩次旋轉豹休，步驟如下：

1. 圍繞根節(jié)點的左孩子進行RR旋轉炊昆。
2. 圍繞根節(jié)點進行LL旋轉。

LR的旋轉示意圖如下：

在這里插入圖片描述

RL的旋轉：RL失去平衡的情況下也需要進行兩次旋轉威根，旋轉方法與LR旋轉對稱凤巨，步驟如下：

1. 圍繞根節(jié)點的右孩子進行LL旋轉。
2. 圍繞根節(jié)點進行RR旋轉洛搀。

RL的旋轉示意圖如下：

在這里插入圖片描述

? \color{pink}{\spadesuit}?

B-Tree（平衡多路查找樹）

B-Tree是為磁盤等外存儲設備設計的一種平衡查找樹敢茁。因此在講B-Tree之前先了解下磁盤的相關知識。

系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存時是以磁盤塊（block）為基本單位的留美，位于同一個磁盤塊中的數(shù)據(jù)會被一次性讀取出來彰檬，而不是需要什么取什么伸刃。

InnoDB存儲引擎中有頁（Page）的概念，頁是其磁盤管理的最小單位逢倍。InnoDB存儲引擎中默認每個頁的大小為16KB捧颅，可通過參數(shù)innodb_page_size將頁的大小設置為4K、8K较雕、16K碉哑，在MySQL中可通過如下命令查看頁的大小：

mysql> show variables like 'innodb_page_size';

而系統(tǒng)一個磁盤塊的存儲空間往往沒有這么大郎笆，因此InnoDB每次申請磁盤空間時都會是若干地址連續(xù)磁盤塊來達到頁的大小16KB谭梗。InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時會以頁為基本單位，在查詢數(shù)據(jù)時如果一個頁中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置宛蚓，這將會減少磁盤I/O次數(shù)激捏，提高查詢效率。

B-Tree結構的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤塊凄吏。為了描述B-Tree远舅，首先定義一條記錄為一個二元組[key, data] ，key為記錄的鍵值痕钢，對應表中的主鍵值图柏，data為一行記錄中除主鍵外的數(shù)據(jù)。對于不同的記錄任连，key值互不相同蚤吹。

一棵m階的B-Tree有如下特性：

1. 每個節(jié)點最多有m個孩子。
2. 除了根節(jié)點和葉子節(jié)點外随抠，其它每個節(jié)點至少有Ceil(m/2)個孩子裁着。
3. 若根節(jié)點不是葉子節(jié)點，則至少有2個孩子
4. 所有葉子節(jié)點都在同一層拱她，且不包含其它關鍵字信息
5. 每個非終端節(jié)點包含n個關鍵字信息（P0,P1,…Pn, k1,…kn）
6. 關鍵字的個數(shù)n滿足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)為關鍵字二驰，且關鍵字升序排序。
8. Pi(i=1,…n)為指向子樹根節(jié)點的指針秉沼。P(i-1)指向的子樹的所有節(jié)點關鍵字均小于ki桶雀，但都大于k(i-1)

B-Tree中的每個節(jié)點根據(jù)實際情況可以包含大量的關鍵字信息和分支，如下圖所示為一個3階的B-Tree：

在這里插入圖片描述

每個節(jié)點占用一個盤塊的磁盤空間唬复，一個節(jié)點上有兩個升序排序的關鍵字和三個指向子樹根節(jié)點的指針矗积，指針存儲的是子節(jié)點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數(shù)據(jù)的范圍域敞咧。以根節(jié)點為例漠魏，關鍵字為17和35，P1指針指向的子樹的數(shù)據(jù)范圍為小于17妄均，P2指針指向的子樹的數(shù)據(jù)范圍為17~35柱锹，P3指針指向的子樹的數(shù)據(jù)范圍為大于35。

模擬查找關鍵字29的過程：

根據(jù)根節(jié)點找到磁盤塊1丰包，讀入內(nèi)存。【磁盤I/O操作第1次】
比較關鍵字29在區(qū)間（17,35）洼冻，找到磁盤塊1的指針P2骤宣。
根據(jù)P2指針找到磁盤塊3，讀入內(nèi)存寄症≈姹耄【磁盤I/O操作第2次】
比較關鍵字29在區(qū)間（26,30），找到磁盤塊3的指針P2有巧。
根據(jù)P2指針找到磁盤塊8释漆，讀入內(nèi)存±河【磁盤I/O操作第3次】
在磁盤塊8中的關鍵字列表中找到關鍵字29男图。
分析上面過程，發(fā)現(xiàn)需要3次磁盤I/O操作甜橱，和3次內(nèi)存查找操作逊笆。由于內(nèi)存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率岂傲。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素难裆。B-Tree相對于AVLTree縮減了節(jié)點個數(shù)，使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用镊掖，從而提高了查詢效率乃戈。
? \color{pink}{\spadesuit}?

B+Tree

B+Tree是在B-Tree基礎上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結構堰乔，InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結構偏化。

從上一節(jié)中的B-Tree結構圖中可以看到每個節(jié)點中不僅包含數(shù)據(jù)的key值，還有data值镐侯。而每一個頁的存儲空間是有限的侦讨，如果data數(shù)據(jù)較大時將會導致每個節(jié)點（即一個頁）能存儲的key的數(shù)量很小，當存儲的數(shù)據(jù)量很大時同樣會導致B-Tree的深度較大苟翻，增大查詢時的磁盤I/O次數(shù)韵卤，進而影響查詢效率。在B+Tree中崇猫，所有數(shù)據(jù)記錄節(jié)點都是按照鍵值大小順序存放在同一層的葉子節(jié)點上沈条，而非葉子節(jié)點上只存儲key值信息，這樣可以大大加大每個節(jié)點存儲的key值數(shù)量诅炉，降低B+Tree的高度蜡歹。

B+Tree和B-Tree的區(qū)別

B-Tree

• 每個節(jié)點都存儲key和data屋厘，所有節(jié)點組成這棵樹，并且葉子節(jié)點指針為null月而，葉子結點不包含任何關鍵字信息

B+Tree

• 所有的葉子結點中包含了全部關鍵字的信息汗洒，非葉子節(jié)點只存儲鍵值信息，及指向含有這些關鍵字記錄的指針父款，且葉子結點本身依關鍵字的大小自小而大的順序鏈接溢谤，所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最泻┰堋）關鍵字世杀。 (而B樹的非終節(jié)點也包含需要查找的有效信息)
• 所有葉子節(jié)點之間都有一個鏈指針。
• 數(shù)據(jù)記錄都存放在葉子節(jié)點中肝集。

由于B+Tree的非葉子節(jié)點只存儲鍵值信息瞻坝，假設每個磁盤塊能存儲4個鍵值及指針信息，則變成B+Tree后其結構如下圖所示：

在這里插入圖片描述

通常在B+Tree上有兩個頭指針包晰，一個指向根節(jié)點湿镀，另一個指向關鍵字最小的葉子節(jié)點，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈式環(huán)結構伐憾。因此可以對B+Tree進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找勉痴，另一種是從根節(jié)點開始，進行隨機查找树肃。

可能上面例子中只有22條數(shù)據(jù)記錄蒸矛，看不出B+Tree的優(yōu)點，下面做一個推算：

InnoDB存儲引擎中頁的大小為16KB胸嘴，一般表的主鍵類型為INT（占用4個字節(jié)）或BIGINT（占用8個字節(jié)）雏掠，指針類型也一般為4或8個字節(jié)，也就是說一個頁（B+Tree中的一個節(jié)點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值劣像，為方便計算乡话，這里的K取值為10³。也就是說一個深度為3的B+Tree索引可以維護10³ * 10³ * 10³ = 10億條記錄耳奕。

實際情況中每個節(jié)點可能不能填充滿绑青，因此在數(shù)據(jù)庫中，B+Tree的高度一般都在2-4層屋群。mysql的InnoDB存儲引擎在設計時是將根節(jié)點常駐內(nèi)存的闸婴，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。

數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）芍躏。上面的B+Tree示例圖在數(shù)據(jù)庫中的實現(xiàn)即為聚集索引邪乍，聚集索引的B+Tree中的葉子節(jié)點存放的是整張表的行記錄數(shù)據(jù)。輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點并不包含行記錄的全部數(shù)據(jù)，而是存儲相應行數(shù)據(jù)的聚集索引鍵庇楞，即主鍵榜配。當通過輔助索引來查詢數(shù)據(jù)時，InnoDB存儲引擎會遍歷輔助索引找到主鍵姐刁，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)芥牌。

聚集索引和非聚集索引區(qū)別?

聚集索引(clustered index):

聚集索引表記錄的排列順序和索引的排列順序一致，所以查詢效率快聂使，只要找到第一個索引值記錄，其余就連續(xù)性的記錄在物理也一樣連續(xù)存放谬俄。聚集索引對應的缺點就是修改慢柏靶，因為為了保證表中記錄的物理和索引順序一致，在記錄插入的時候溃论，會對數(shù)據(jù)頁重新排序屎蜓。
聚集索引類似于新華字典中用拼音去查找漢字，拼音檢索表于書記順序都是按照a~z排列的钥勋，就像相同的邏輯順序于物理順序一樣炬转，當你需要查找a，ai兩個讀音的字算灸，或是想一次尋找多個傻(sha)的同音字時扼劈，也許向后翻幾頁，或緊接著下一行就得到結果了菲驴。

非聚合索引(nonclustered index):

非聚集索引指定了表中記錄的邏輯順序荐吵，但是記錄的物理和索引不一定一致，兩種索引都采用B+樹結構赊瞬，非聚集索引的葉子層并不和實際數(shù)據(jù)頁相重疊先煎，而采用葉子層包含一個指向表中的記錄在數(shù)據(jù)頁中的指針方式。非聚集索引層次多巧涧，不會造成數(shù)據(jù)重排薯蝎。
非聚集索引類似在新華字典上通過偏旁部首來查詢漢字，檢索表也許是按照橫谤绳、豎占锯、撇來排列的，但是由于正文中是a~z的拼音順序闷供，所以就類似于邏輯地址于物理地址的不對應烟央。同時適用的情況就在于分組，大數(shù)目的不同值歪脏，頻繁更新的列中疑俭，這些情況即不適合聚集索引。

根本區(qū)別：

聚集索引和非聚集索引的根本區(qū)別是表記錄的排列順序和與索引的排列順序是否一致婿失。

為什么說B+比B樹更適合實際應用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引钞艇？

1.B+的磁盤讀寫代價更低

B+的內(nèi)部結點并沒有指向關鍵字具體信息的指針啄寡。因此其內(nèi)部結點相對B樹更小。如果把所有同一內(nèi)部結點的關鍵字存放在同一盤塊中哩照，那么盤塊所能容納的關鍵字數(shù)量也越多挺物。一次性讀入內(nèi)存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數(shù)也就降低了飘弧。

2.B+tree的查詢效率更加穩(wěn)定

由于非終結點并不是最終指向文件內(nèi)容的結點识藤，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路次伶。所有關鍵字查詢的路徑長度相同痴昧，導致每一個數(shù)據(jù)的查詢效率相當。

索引和B+樹及B-Tree關聯(lián)的冠王，要更好的了解兩者赶撰，你還需要去了解?數(shù)據(jù)庫索引是啥，有需要的童鞋可以看看柱彻。

原文鏈接:https://www.cnblogs.com/vianzhang/p/7922426.html