為什麼Innodb選擇B+樹索引

B+樹結構 and 為什麼

數據結構演示網頁，可以通過網頁觀察數據結構的生成，更直觀的理解

索引結構默認使用B+樹，而不是二叉樹，紅黑樹，b樹，哈希

為什麼？

什麼是索引

索引就是一種單獨的數據結構，用來對數據庫的數據進行快速檢索的數據結構，他針對某個表中的一列或者多列。

簡單的説就相當於圖書的目錄，你可以根據目錄快速找到自己想要的內容

二叉樹

每個根節點最多有兩個子節點

二叉搜索樹 -- 左子樹小於根節點，右子樹大於父節點，二分搜索的結構化

最好情況 -- logN

最壞情況 -- n

紅黑樹

自平衡的二叉搜索樹

特性：

• 每個節點都是黑色或者紅色的
• 根節點是黑色的
• 如果一個節點是紅色，他的子節點一定是黑色
• 從一個節點到該節點所有葉子節點的路徑上包含相同數據的黑色節點
• 所有葉子節點都是黑色的（葉子節點的值為null）

即使紅黑樹 也是一個二叉樹，隨着數據量的增多，紅黑樹的層級會越來越深，檢索速度會越來越慢

B-樹

紅黑樹是一個二叉樹，那B樹就是一個多叉樹，B樹每個節點有多個分支，即多叉樹

特點：

• 在B樹中，所有葉子結點和非葉子節點都會儲存數據！！
• n階的B樹只能儲存n-1個key, n個指針
• 一旦節點儲存的數量達到n，就會發生裂變，中間元素向上分裂

B+樹

B+樹是B樹的一個變種

和B樹的區別:

• 只有葉子結點才會儲存數據！！
• 非葉子節點只會儲存索引
• 葉子節點之間會形成一個鏈表，這個鏈表的所有元素都是有序排列的

Mysql的B+樹

Mysql對經典的B+樹進行了優化，在原有的基礎上，增加了指向相鄰葉子節點的指針，把一個單向的鏈表變成了雙向鏈表，這樣就更方便查找了

這種結構可以很方便進行範圍查找和排序查找

B+樹只有葉子結點儲存數據

為什麼使用B+樹

需要結合Innodb的邏輯儲存結構來説，B+樹和B-樹的節點都儲存在一個頁上面，頁的大小是固定的

• 表空間
• 段
• 區 -- 一個區有64頁, 大小1M
• 頁 -- 一頁大小16k ，16 * 1024
• 行 -- 數據是按行進行存放的

為什麼使用B+樹

• 和二叉樹相比。B+樹層級更低，索引效率高

• 和B樹相比。B樹和B+樹的索引的葉子節點都是儲存在一個頁上面的，而頁的大小是固定的。

• B+樹的非葉子結點只存儲鍵值和指針，而B樹連帶數據一起存儲。這樣就導致相同大小的頁，使用B樹的鍵值和指針會變少，就會增加樹的高度，增加IO次數，導致性能降低
• 和哈希相比，B+樹支持範圍查找，排序查找，而哈希不支持

思考題：

假設：一行數據大小為1k，一頁可以儲存16行這樣的數據。Innodb的指針佔用6個字節的空間，鍵值採用BigInt，查8個字節的空間，問能儲存多少數據

索引由鍵值和指針組成，n個鍵，n+1個指針

n*8 + (n+1) * 6 = 16 * 1024 , 計算得出 n = 1170

高度為2：

​ 1171 * 16 = 18736

高度為3

​ 1171 * 1171 * 16 = 21,939,856