一、B-樹
1. 常見的搜索結(jié)構(gòu)
| 種類 | 數(shù)據(jù)格式 | 時間復(fù)雜度 |
|---|---|---|
| 順序查找 | 無要求 | O(N) |
| 二分查找 | 有序 | O(log2N) |
| 二叉搜索樹 | 無要求 | O(N) |
| 二叉平衡樹(紅黑樹和AVL樹) | 無要求 | O(log2N) |
| 哈希 | 無要求 | O(1) |
以上結(jié)構(gòu)適合用于數(shù)據(jù)量相對不是很大，能夠一次性存放在內(nèi)存中，進(jìn)行數(shù)據(jù)查找的場景。如果數(shù)據(jù)量很大，比如有100G數(shù)據(jù)，無法一次放進(jìn)內(nèi)存中，那就只能放在磁盤上了，如果放在磁盤上，有需要搜索某些數(shù)據(jù)，那么如果處理呢？那么我們可以考慮將存放關(guān)鍵字及其映射的數(shù)據(jù)的地址放到一個內(nèi)存中的搜索樹的節(jié)點中，那么要訪問數(shù)據(jù)時，先取這個地址去磁盤訪問數(shù)據(jù)。
使用平衡二叉樹搜索樹的缺陷：
平衡二叉樹搜索樹的高度是logN，這個查找次數(shù)在內(nèi)存中是很快的。但是當(dāng)數(shù)據(jù)都在磁盤中時，訪問磁盤速度很慢，在數(shù)據(jù)量很大時，logN次的磁盤訪問，是一個難以接受的結(jié)果。
使用哈希表的缺陷：
哈希表的效率很高是O(1)，但是一些極端場景下某個位置沖突很多，導(dǎo)致訪問次數(shù)劇增，也是難以接受的。
那如何加速對數(shù)據(jù)的訪問呢？
- 提高IO的速度(SSD相比傳統(tǒng)機械硬盤快了不少，但是還是沒有得到本質(zhì)性的提升)
- 降低樹的高度—多叉樹平衡樹
2. B樹概念
1970年，R.Bayer和E.mccreight提出了一種適合外查找的樹，它是一種平衡的多叉樹，稱為B樹(后面有一個B的改進(jìn)版本B+樹，然后有些地方的B樹寫的的是B-樹，注意不要誤讀成"B減樹")。一棵m階(m>2)的B樹，是一棵平衡的M路平衡搜索樹，可以是空樹或者滿足以下性質(zhì)：
- 根節(jié)點至少有兩個孩子
- 每個分支節(jié)點都包含
k-1個關(guān)鍵字和k個孩子，其中ceil(m/2) ≤ k ≤ mceil是向上取整函數(shù)- 每個葉子節(jié)點都包含k-1個關(guān)鍵字，其中 ceil(m/2) ≤ k ≤ m
- 所有的葉子節(jié)點都在同一層
- 每個節(jié)點中的關(guān)鍵字從小到大排列，節(jié)點當(dāng)中k-1個元素正好是k個孩子包含的元素的值域劃分
- 每個結(jié)點的結(jié)構(gòu)為：（n，A0，K1，A1，K2，A2，… ，Kn，An） 其中，Ki(1≤i≤n)為關(guān)鍵字，且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)為指向子樹根結(jié)點的指針。且Ai所指子樹所有結(jié)點中的關(guān)鍵字均小于Ki+1。n為結(jié)點中關(guān)鍵字的個數(shù)，滿足ceil(m/2)-1≤n≤m-1。
3. B-樹的查找
假設(shè)每個節(jié)點有 n 個 key值，被分割為 n+1 個區(qū)間，一般而言，根節(jié)點都在內(nèi)存中，B-樹以每個節(jié)點為一次磁盤 IO，比如上圖中，若搜索 key 為 49 的節(jié)點，首先在根節(jié)點進(jìn)行二分查找（因為 keys 有序，二分最快），判斷 根節(jié)點的最小節(jié)點75都比49大， 所以定位到75節(jié)點的左孩子節(jié)點，此時進(jìn)行一次磁盤 IO，將該節(jié)點從磁盤讀入內(nèi)存，接著繼續(xù)進(jìn)行上述過程，直到找到該 key 為止。
4. B-樹的插入分析
插入元素的基本操作：
假設(shè)該B樹為M階，M = 3
分裂節(jié)點的基本操作：
這里我們看出B樹是天然平衡的，因為它是向右和向上增長的，根節(jié)點的分裂會增加一層。
這里我們還需要注意的是：
- 新插入的節(jié)點一定是在葉子插入，葉子沒有孩子，不影響關(guān)鍵字和孩子之間的關(guān)系。
- 葉子節(jié)點滿了，分裂出一個兄弟，提取中位數(shù)，向父親插入一個值和一個孩子。
二、B+樹和B*樹
1. B+樹
B+樹是B樹的變形，是在B樹基礎(chǔ)上優(yōu)化的多路平衡搜索樹，B+樹的規(guī)則跟B樹基本類似，但是又
在B樹的基礎(chǔ)上做了以下幾點改進(jìn)優(yōu)化：
- 分支節(jié)點的子樹指針與關(guān)鍵字個數(shù)相同
- 分支節(jié)點的子樹指針
p[i]指向關(guān)鍵字值大小在[k[i]，k[i+1])區(qū)間之間- 所有葉子節(jié)點增加一個鏈接指針鏈接在一起
- 所有關(guān)鍵字及其映射數(shù)據(jù)都在葉子節(jié)點出現(xiàn)
B+ 樹的特征
- B+樹內(nèi)部有兩種結(jié)點，一種是索引結(jié)點，一種是葉子結(jié)點。
- B+樹的索引結(jié)點并不會保存記錄，只用于索引，所有的數(shù)據(jù)都保存在B+樹的葉子結(jié)點中。而B樹則是所有結(jié)點都會保存數(shù)據(jù)。
- B+樹的葉子結(jié)點都會被連成一條鏈表。葉子本身按索引值的大小從小到大進(jìn)行排序。即這條鏈表是 從小到大的。多了條鏈表方便范圍查找數(shù)據(jù)。
- B樹的所有索引值是不會重復(fù)的，而B+樹 非葉子結(jié)點的索引值 最終一定會全部出現(xiàn)在 葉子結(jié)點中。
B+樹的插入過程
B+樹的插入過程跟B樹基本是類似的，細(xì)節(jié)區(qū)別在于：第一次插入兩層節(jié)點，一層做分支，另一層做根。
后面一樣往葉子去插入，插入滿了以后，分裂一半給兄弟，轉(zhuǎn)換成往父親插入一個key和一個孩子，孩子就是兄弟。key是兄弟的第一個最小值的key。
B+樹的詳細(xì)插入過程如下：
B樹和B+樹的對比：
- B樹好處：
B樹的每一個結(jié)點都包含key(索引值) 和 value(對應(yīng)數(shù)據(jù))，因此方位離根結(jié)點近的元素會更快速。（相對于B+樹）- B樹的不足：
不利于范圍查找(區(qū)間查找)，如果要找 0~100的索引值，那么B樹需要多次從根結(jié)點開始逐個查找。
而B+樹由于葉子結(jié)點都有鏈表，且鏈表是以從小到大的順序排好序的，因此可以直接通過遍歷鏈表實現(xiàn)范圍查找。
2. B*樹
B*樹是B+樹的變形，在B+樹的 非根和非葉子節(jié)點再增加指向兄弟節(jié)點的指針。
B+樹的分裂：
當(dāng)一個結(jié)點滿時，分配一個新的結(jié)點，并將原結(jié)點中1/2的數(shù)據(jù)復(fù)制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點的指針；B+樹的分裂只影響原結(jié)點和父結(jié)點，而不會影響兄弟結(jié)點，所以它不需要指向兄弟的指針。
B*樹的分裂
當(dāng)一個結(jié)點滿時，如果它的下一個兄弟結(jié)點未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點中，再在原結(jié)點插入關(guān)鍵字，最后修改父結(jié)點中兄弟結(jié)點的關(guān)鍵字（因為兄弟結(jié)點的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點，最后在父結(jié)點增加新結(jié)點的指針。 所以，B*樹分配新結(jié)點的概率比B+樹要低，空間使用率更高；
總結(jié)：
通過以上介紹，大致將B樹，B+樹，B*樹總結(jié)如下：
B樹：有序數(shù)組+平衡多叉樹；B+樹：有序數(shù)組鏈表+平衡多叉樹；B*樹：一棵更豐滿的，空間利用率更高的B+樹。
注意：
三、B-樹的應(yīng)用
1. 索引
B-樹最常見的應(yīng)用就是用來做索引。索引通俗的說就是為了方便用戶快速找到所尋之物，比如：書籍目錄可以讓讀者快速找到相關(guān)信息，hao123網(wǎng)頁導(dǎo)航網(wǎng)站，為了讓用戶能夠快速的找到有價值的分類網(wǎng)站，本質(zhì)上就是互聯(lián)網(wǎng)頁面中的索引結(jié)構(gòu)。
MySQL官方對索引的定義為：索引(index)是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，簡單來說：索引就是數(shù)據(jù)結(jié)構(gòu)。
當(dāng)數(shù)據(jù)量很大時，為了能夠方便管理數(shù)據(jù)，提高數(shù)據(jù)查詢的效率，一般都會選擇將數(shù)據(jù)保存到數(shù)據(jù)庫，因此數(shù)據(jù)庫不僅僅是幫助用戶管理數(shù)據(jù)，而且數(shù)據(jù)庫系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法，該數(shù)據(jù)結(jié)構(gòu)就是索引。
2. MySQL索引簡介
MySQL是目前非常流行的開源關(guān)系型數(shù)據(jù)庫，不僅是免費的，可靠性高，速度也比較快，而且擁有靈活的插件式存儲引擎，如下：
MySQL中索引屬于存儲引擎級別的概念，不同存儲引擎對索引的實現(xiàn)方式是不同的。
比如我們建立一張學(xué)生成績表
B+樹索引磁盤數(shù)據(jù)
一般數(shù)據(jù)庫要求主鍵是唯一的，比如MySQL、建表的主鍵，就是B+樹的key，B+樹的value是存儲一行數(shù)據(jù)的磁盤地址。
這里我們需要注意的是：分支節(jié)點也是需要存在磁盤中的，因為數(shù)據(jù)量大了，內(nèi)存是存不下的。分支節(jié)點中應(yīng)該是磁盤地址但是分支節(jié)點理論應(yīng)該盡量被緩存到cache中。
一般數(shù)據(jù)庫要求主鍵值是不重復(fù)唯一值字段: 電話、身份證號碼適合。名字、地址不適合。 沒有字段能保持唯一，可以考慮自增主鍵 (其實他自己建立一個自增整數(shù)做主鍵)。一般數(shù)據(jù)庫不要求索引唯一，像mysql建立索引可以考慮使用B+樹或者Hash表，數(shù)據(jù)結(jié)構(gòu)允許冗余
2.1 MyISAM
MyISAM引擎是MySQL5.5.8版本之前默認(rèn)的存儲引擎，不支持事物，支持全文檢索，使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點的data域存放的是數(shù)據(jù)記錄的地址，其結(jié)構(gòu)如下：
說明：
-
“葉節(jié)點的data域存放的是數(shù)據(jù)記錄的地址” 方便了
索引樹和主鍵樹映射同樣的數(shù)據(jù)。 - B樹節(jié)點數(shù)據(jù)都在磁盤文件中，訪問節(jié)點都是IO行為，只是他們會見
熱數(shù)據(jù)緩存在Cache中。索引文件中存儲的是數(shù)據(jù)文件的地址。
2.2 InnoDB
InnoDB存儲引擎支持事務(wù)，其設(shè)計目標(biāo)主要面向在線事務(wù)處理的應(yīng)用，從MySQL數(shù)據(jù)庫5.5.8版本開始，InnoDB存儲引擎是默認(rèn)的存儲引擎。InnoDB支持B+樹索引、全文索引、哈希索引。但I(xiàn)nnoDB使用B+Tree作為索引結(jié)構(gòu)時，具體實現(xiàn)方式卻與MyISAM截然不同。
第一個區(qū)別是： InnoDB的數(shù)據(jù)文件本身就是索引文件。MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址。而InnoDB索引，表數(shù)據(jù)文件本身就是按B+Tree組織的一個索引結(jié)構(gòu)，這棵樹的葉節(jié)點data域保存了完整的數(shù)據(jù)記錄。這個索引的key是數(shù)據(jù)表的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。
第二個區(qū)別是： InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址,所有輔助索引都引用主鍵作為data域。
建立索引的時候，索引樹的葉子節(jié)點和主鍵樹葉子節(jié)點中數(shù)據(jù)不一樣，沒辦法直接映射
文章來源：http://www.zghlxwxcb.cn/news/detail-602825.html
先用name，name對應(yīng)主鍵id，再用主鍵id再去主鍵樹搜索一次也就是說他用索引查找，要查找兩次文章來源地址http://www.zghlxwxcb.cn/news/detail-602825.html
到了這里，關(guān)于【高階數(shù)據(jù)結(jié)構(gòu)】B樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
