前言
昨天寫完了二叉樹、平衡二叉樹、紅黑樹的一部分，今天把剩餘的B-Tree、以及B+Tree整理出來。
1、B-Tree
1.1定義：
B-tree（多路搜尋樹，并不是二叉的）是一種常見的資料結構。使用B-tree結構可以顯著減少定位記錄時所經曆的中間過程，進而加快存取速度 。 ----------百度百科
與二叉樹相比，B-Tree利用
多個分支
（二叉樹隻有2個分支）節點，
減少了擷取記錄時所經曆的節點數
，進而達到節省存取時間的目的。
B-Tree結構的資料可以讓系統高效的找到資料所在的磁盤塊。是以B-Tree一般使用在磁盤等外儲存設備中的存儲結構中。
1.2結構：
圖檔摘自：https://blog.csdn.net/hao65103940/article/details/89032538
1.3分析：
- 從上圖的結構中我們可以看到在B-Tree中每個結點存儲了
鍵值和資料
指針
- 并且我們可以看到在B-Tree中每個結點到葉子結點的
高度都是相同
- 每個結點就是對應的鍵值，這樣在擷取資料時，隻要找到鍵值就可以擷取到對應的資料，不需要再進行定位資料的位置，加快了速度。
- 查詢資料時先通過鍵值定位到所在的
磁盤塊
1.4特點：
- 每個節點最多有m個孩子（m代表階數）
- 除了根節點和葉子節點外，其它每個節點至少有Ceil(m/2)個孩子
- 若根節點不是葉子節點，則至少有2個孩子
- 所有葉子節點都在同一層，且不包含其它關鍵字資訊
- 非葉子結點的關鍵字個數， ki(i=1,…n)為關鍵字，且關鍵字升序排序（
k[i]<k[i+1]
- 非葉子結點的關鍵字個數=指向兒子的指針個數-1
- 非葉子結點的指針：P[1], P[2], …,P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1],K[i])的子樹
1.5操作：
查詢：在B-Tree中，進行查詢操作時通過關鍵字就可以實作擷取到對應的資料。
查詢結構中的28：
- 首先在磁盤塊1中進行查找，找到對應的磁盤指針P2，
- 通過P2進入磁盤塊3，
- 在磁盤塊3中進行判斷找到P2，
- 通過P2找到磁盤塊8，
- 在磁盤塊8中查詢關鍵字為28的資料。
新增：在B-Tree中進行新增結點時需要進行裂變。
新增結點18：
- 首先在磁盤塊1中判斷18對應的是P2
- 通過P2進入磁盤塊3
- 在磁盤塊中找到P1
- 在P1中新增葉子結點磁盤塊12
- 将關鍵字18以及對應的資料存放在磁盤塊12中
删除：删除操作和新增操作類似也可能發生裂變。
1.6總結：
- 插入或者删除元素都會導緻節點發生裂變反應，如此才讓B樹能夠始終保持多路平衡，這是B-Tree的一個優勢：自平衡。
- B樹主要應用于檔案系統以及部分資料庫索引，如MongoDB，大部分關系型資料庫索引則是使用B+樹實作。
- B-Tree所經過的結點數量要比平衡二叉樹少很多，是以可以減少磁盤的IO，這對性能的提升很大。
2、B+Tree
2.1定義：
B+tree 是在 B- tree基礎上的優化，是一種更适合存儲索引的資料結構。
2.2結構：
圖檔摘自：https://blog.csdn.net/hao65103940/article/details/89032538
2.3特點：
在B+Tree中，它的結構和B-Tree很像，但是它有如下自己的特征：
- 非葉子結點隻存儲自己的關鍵字資訊
- 資料記錄都存放在葉子節點中
- 所有葉子節點之間有一個鍊指針
2.4總結：
- 那為什麼要将資料隻存儲在葉子結點呢，這是因為在磁盤中，
頁
data
深度較大
IO次數
- 為了解決這個問題，實作了B+Tree，在B+Tree中，所有資料記錄節點都是按照
鍵值
key
key值數量
- 所有葉子節點形成一個有序連結清單（
鍊式環結構
- innodb存儲引擎使用B+Tree做索引結構。
- 資料庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）。上面的B+Tree示例圖在資料庫中的實作即為聚集索引，聚集索引的B+Tree中的葉子節點存放的是整張表的行記錄資料。
- 輔助索引與聚集索引的差別在于輔助索引的葉子節點并不包含行記錄的全部資料，而是存儲相應行資料的聚集索引鍵，即主鍵。當通過輔助索引來查詢資料時，InnoDB存儲引擎會周遊輔助索引找到主鍵，然後再通過主鍵在聚集索引中找到完整的行記錄資料。
結語：
以上就是自己對B-Tree以及B+Tree的整理和總結，總結的不完善，也不夠深度，是最簡單的了解性總結，是以也是幫助自己加深對這部分知識的認識，以後了解的更多了也會繼續記錄。
我是走在學習路上、膜拜大佬的程式員！