一文了解mysql索引的數據結構為什么要用B+樹

更新時間：2022年04月25日 14:32:35 作者：YuShiwen?

這篇文章主要介紹了一文了解mysql索引的數據結構為什么用B+樹，在節(jié)點中存儲某段數據的首地址，并且B+樹的葉子節(jié)點用了一個鏈表串聯起來，便于范圍查找，下文利用各種索引的數據結構的方法與B+樹做對比，看看它的優(yōu)勢到底是什么，感興趣的小伙伴可以參考一下

1. Hash表？No

因考慮到在數據檢索的過程中經常會有范圍的查詢（如下），而hash表不能提供這種功能。

SELECT * FROM hero WHERE age>5 AND age<20;

使用哈希算法實現的索引雖然可以做到快速檢索數據，但是沒辦法做數據高效范圍查找，因此哈希索引是不適合作為 Mysql 的底層索引的數據結構。

2. 二叉查找樹(BST)？No

二叉查找樹（Binary Search Tree）雖然可以達到范圍搜索，但是在樹的插入過程中，如果插入的數據本來就是有順序的，那么就會形成一條鏈（如下），它的最壞情況是O(n)。

3. 紅黑樹？No

紅黑樹雖然看似達到了平衡狀態(tài)，但是也會有極端情況存在，和上述BST樹一樣，雖然不會成為鏈狀，但是紅黑樹會存在右傾的現象。

在數據庫中的基本主鍵自增操作，主鍵一般都是數百萬數千萬的，如果紅黑樹存在這種問題，對于查找性能而言也是巨大的消耗，我們數據庫不可能忍受這種無意義的等待的。

4. 平衡二叉樹(AVL)？差那么二點意思

平衡二叉樹，英文翻譯為Balanced Binary Tree，為啥叫AVL呢？ AVL 是大學教授G.M. Adelson-Velsky 和 E.M. Landis 名稱的縮寫，他們提出的平衡二叉樹的概念，為了紀念他們，將平衡二叉樹稱為 AVL樹。

AVL樹本質上是一顆二叉查找樹，但是它又具有以下特點：

它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，
左右兩個子樹也都是一棵平衡二叉樹。

它不存在紅黑樹這種右傾的現象，也具備數據高效范圍查找的能力，但是數據庫查詢數據的瓶頸在于磁盤的IO，樹節(jié)點在磁盤空間中存儲可能是不連續(xù)的，假設我們一次IO讀取一個樹的節(jié)點，此次讀入內存的這頁中沒有其他樹的節(jié)點，那么每讀取一個樹的節(jié)點，就要進行一次IO，這是多么消耗時間啊，所以我們設計數據庫索引時需要首先考慮怎么盡可能減少磁盤 IO 的次數。磁盤讀取依靠的是機械運動，分為尋道時間、旋轉延遲、傳輸時間三個部分，這三個部分耗時相加就是一次磁盤IO的時間；這個花費的時間成本是內存訪問的十幾萬倍左右。正是由于磁盤IO是非常昂貴的操作，所以計算機操作系統(tǒng)對此做了優(yōu)化：預讀；每一次IO時，不僅僅把當前磁盤地址的數據加載到內存，同時也把相鄰數據也加載到內存緩沖區(qū)中。因為局部預讀原理說明：當訪問一個地址數據的時候，與其相鄰的數據很快也會被訪問到。每次磁盤IO讀取的數據我們稱之為一頁（page）。一頁的大小與操作系統(tǒng)有關，一般為4k或者8k。這也就意味著讀取一頁內數據的時候，實際上發(fā)生了一次磁盤IO。

相關術語解釋：

扇區(qū)(sector)：

磁盤上的每個磁道被等分成多個弧段，這個弧段便稱作扇區(qū)（sector）。
扇區(qū)是磁盤物理層面的名稱，它是實際發(fā)生讀寫的最底層。

磁盤塊(IO Block)：

操作系統(tǒng)不與扇區(qū)直接進行交互，因為一般情況下一個扇區(qū)是512byte，如果1T去用512byte進行劃分，那劃分的地址空間太多了，為了讓操作系統(tǒng)能夠尋址到更大的地址空間，操作系統(tǒng)將相鄰的扇區(qū)組合在一起，形成一個塊，對塊進行管理。每個磁盤塊可以包括 2、4、8、16、32 或 64 個扇區(qū)，這便是磁盤塊（IO Block）。
磁盤塊是操作系統(tǒng)中出現的名稱，文件系統(tǒng)讀寫數據的最小單位，它同時也被叫做磁盤簇。

頁(page)：