- GreatSQL社區原創內容未經授權不得隨意使用，轉載請聯系小編并注明來源，
- GreatSQL是MySQL的國產分支版本，使用上與MySQL一致，
前文回顧
實作一個簡單的Database1(譯文）
實作一個簡單的Database2(譯文）
實作一個簡單的Database3(譯文）
實作一個簡單的Database4(譯文）
實作一個簡單的Database5(譯文）
實作一個簡單的Database6(譯文）
譯注：cstsck在github維護了一個簡單的、類似sqlite的資料庫實作，通過這個簡單的專案，可以很好的理解資料庫是如何運行的，本文是第七篇，主要是對B-tree的介紹
Part 7 B-Tree簡介
B-tree是SQLite用來表示表和索引的資料結構，所以B-tree是非常中心的想法，這個主題主要是介紹B-tree資料結構，所以不會有任何的代碼，
為什么說對于資料庫來說，樹是非常好的資料結構呢？
- 查找特定的value很快（對數時間花銷，loga N）
- 插入一行或者對查詢到的資料洗掉很快（再平衡使用常量時間）
- 遍歷一個范圍內的value很快（不像hash map）
B-tree不同于二叉樹（“B”可能代表發明人的名字，但也可以代表“Balanced”），這里是一個B-tree例子：
B-Tree 例子(https://en.wikipedia.org/wiki/File:B-tree.svg)
不像二叉樹每個節點只能有兩個子節點，B-tree的每個節點可以有兩個以上的子節點，每個節點最多可以有 m 個子節點，其中 m 叫做樹的“order”（或者叫“階”），為了保持樹的盡量平衡，我們還要求節點必須至少有 m / 2 個子節點（四舍五入），
但還有一些例外：
- 葉子節點沒有子節點
- 根節點的子節點數可以少于 m，但至少要有兩個
- 如果根節點也是葉子節點（樹只有一個節點），那它有0個子節點
上面的描述的是一個B-tree，SQLite用它來存盤索引，為了存盤表資料，SQLites使用一種B-tree的變體，稱為B+tree，
| B-tree | B+ tree | |
|---|---|---|
| 發音 | “Bee Tree” | “Bee Plus Tree” |
| 用來存盤 | 索引 | 表 |
| 內部節點是否存盤key | 是 | 是 |
| 內部節點是否存盤value | 是 | 否 |
| 每個節點的子節點數 | 少 | 多 |
| 內部節點 vs 葉子節點 | 相同結構 | 不同結構 |
在我們開始實作索引之前，我將只討論B+tree，但這里將其稱為 B-tree 或者 btree，
有子節點（children）的節點被稱為“內部”節點（internal node），內部節點和葉子節點在結構上不同：
| m階tree | 內部節點 | 葉子節點 |
|---|---|---|
| 存盤 | key和指向子節點的指標 | key和value |
| key的數目 | 最多m-1個 | 越多越好 |
| 指標的數目 | keys + 1 | 無 |
| value的數目 | 無 | 與key的數目相同 |
| Key的用途 | 用來路由 | 與value成對存盤 |
| 存盤value? | 否 | 是 |
這里通過一個例子來看一下，當插入一個元素時，B-tree是怎樣發生結構變化的，為了讓事情看起來更容易理解，這棵B-tree的階（order）設定為3(m=3)，也就是說：
- 每個內部節點最多有三個子節點(m)
- 每個內部節點最多有兩個key
- 每個內部節點至少兩個子節點（m-1）
- 每個內部節點至少一個key
一棵空樹只有一個節點：根節點，根節點最開始也作為葉子節點，有0個鍵值對（key/value）：
空的btree
如果我們插入兩個鍵值對（超過兩個鍵值對，節點需要分裂，參考上面規則），他們會按順序排序存放在葉子節點中，
一個節點的btree
我們假設了節點的容量是兩個鍵值對兒，當我們插入另外一個的時候，就不得不分裂葉子節點了，分裂后的兩個節點每個存放之前一半的鍵值對，分裂后的兩個節點都變成了內部節點，同時也變成了一個新的節點的子節點，這個新的節點變成了根節點，
兩層的btree
圖中的內部節點（也是根節點）有一個key和兩個指標指向子節點（就是那兩條線），如果我們想查找一個key，key小于或等于5，我們查看左子樹，如果查找的key大于5，就查看右子樹，
現在，準備插入一個新的key "2"，首先，我們查找它將位于哪個葉節點（如果它在樹中存在的話），這樣就到達了左側葉子節點，這個節點是滿的，所以把這個葉子節點進行分裂（split），并在父節點創建新的條目，
四節點的btree
現在繼續增加key，18 和 21 ，現在又到了不得不分裂的情況，但是在父節點中已經沒有空間來增加新的鍵值對兒了，
內部節點沒有空間
解決方法就是分裂根節點為兩個內部節點，然后創建一個新的根節點作為兩個內部節點的父節點，
三層的btree
樹只是在我們分裂根節點的時候才會增加深度，每個葉子節點都有相同的深度和接近相同的數量的鍵值對兒，所以樹能夠保持平衡和快速的進行查找，
我暫時先不討論從樹中洗掉鍵的操作，推遲到實作插入操作以后，
當我們實作這個資料結構時，每個節點都對應一個page，根節點將在page0中存在，節點中的子節點指標將簡單的使用包含子節點的page number，
下一次，我們開始實作btree，
Enjoy GreatSQL ??
關于 GreatSQL
GreatSQL是由萬里資料庫維護的MySQL分支，專注于提升MGR可靠性及性能，支持InnoDB并行查詢特性，是適用于金融級應用的MySQL分支版本，
相關鏈接： GreatSQL社區 Gitee GitHub Bilibili
GreatSQL社區：
捉蟲活動詳情：https://greatsql.cn/thread-97-1-1.html
社區博客有獎征稿詳情：https://greatsql.cn/thread-100-1-1.html
技術交流群：
微信：掃碼添加
GreatSQL社區助手微信好友，發送驗證資訊加群，
)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/526064.html
標籤：其他
上一篇：redis實作主從復制