Mysql索引數據結構

下面列舉了常見的數據結構

• 二叉樹
• 紅黑樹
• Hash表
• B-Tree（B樹）

Select * from t where t.col=5

我們在執行一條查詢的Sql語句時候，在數據量比較大又不加索引的情況下，逐行查詢并進行比對，每次需要從磁盤上查找，每行數據可能在磁盤不同的位置，數據比較靠后的話，一千萬數據可能要比對幾百萬，很耗費資源。

Mysql衡量查詢效率的就是磁盤IO次數，那么Mysql中應該采用什么樣的數據結構存儲數據呢，以及為什么要使用那個數據結構呢。

二叉樹

大多數人都知道，如果加上索引之后。把數據放在二叉樹里面，查詢會快很多，但是還有一種特殊的情況：

把一個遞增列的索引放入二叉樹中，列id作為等于5查詢目標，就會從col為1開始搜索，這樣要搜索幾次?二叉樹插入的數據如果大于本身，會放在父節點的右下角，小的會放在父節點的左下角，因此形成了這樣像鏈表一樣的結構，其實本質還是二叉樹。

需要從根節點遍歷，經過5次的查找，每個節點都存儲在磁盤上，每查一個節點需要跟磁盤做一次IO交互，效率相比之前沒加索引也沒有太大提升,這顯然不是Mysql的索引結構。

紅黑樹

HasMap的數據結構就是紅黑樹，原來是數組加鏈表，現在優化到了數組加紅黑樹。

紅黑樹本質還是二叉樹，還有一個名字又叫平衡二叉樹。當一邊子節點比另一邊高太多的時候，會自動旋轉平衡。當數據量比較大的時候比如1000萬，紅黑樹存儲的高度就可能達到幾十。如果數據量越大樹的高度就會越高。每查一個節點要進行一次磁盤IO交互。樹的高的越高查找效率越低，很顯然紅黑樹也不是Mysql的數據結構，早期版本Mysql有用到紅黑樹，現在版本沒有用到紅黑樹。那么能不能對紅黑樹做點改造。

B-Tree

樹的高的越高查找效率越低，那么將樹高縮小，比如限制在5層，把一層存放更多元素。把一個節點的數據在磁盤同一個區域全部查出來放到內存，只做一次IO查找，就可以查到很多索引信息。B樹又叫平衡多叉樹。

索引值和具體data都在每個節點里，而節點的位置不固定，最好的情況查找值就在第一層。

B樹的特點就是每層節點數目非常多，層數很少，目的就是為了就少磁盤IO次數，B樹在提高了磁盤IO性能的同時并沒有解決元素遍歷的效率低下的問題，由于節點內部每個 key 都帶著 data 域，每次查找到具體節點還要和data進行順序比對，如果查找某個范圍內數據，又需要重新遍歷。正是為了解決這個問題，B+樹應運而生

B樹遍歷全部數據：

B+Tree

B+樹節點只存儲 key 的副本，真實的 key 和 data 域都在葉子節點存儲，數據全部存儲在葉子節，并且每一個節點之間用指針串聯起來，形成鏈表，方便遍歷，可以跨區間訪問，這優點尤其突出在范圍查詢，不需要在一次從根節點到子節點遍歷。

B+樹遍歷全部數據：

數據量大的情況下哪個更快，我想你應該知道了吧！

面試 (MySQL 索引為啥要選擇 B+ 樹)

前言:

每天都在跟 mysql 打交道，你知道執行一條簡單的 select 語句，都經歷了哪些過程嗎？

首先，mysql 主要是由 server 層和存儲層兩部分構成的。server 層主要包括連接器、查詢緩存，分析器、優化器、執行器。存儲層主要是用來存儲和查詢數據的，常用的存儲引擎有 InnoDB、MyISAM，MySQL 5.5.5 版本后使用 InnoDB 作為默認存儲引擎。

連接器

連接器主要負責將 mysql 客戶端和服務端建立連接，連接成功后，會獲取當前連接用戶的權限。這里獲取到的權限對整個連接都有效，一旦連接成功后，如果使用管理員賬號對該用戶更改權限，當前連接中的擁有的權限保持不變，只有等到下次重新連接才會更新權限。

查詢緩存

• 連接成功后，即開始要正式執行 select 語句了，但是在執行查詢之前，mysql 會去看下有沒有該條語句的緩存內容，如果有緩存直接從緩存中讀取并返回數據，不再執行后面的步驟了，結束查詢操作。
• 如果沒有緩存則繼續往后執行，并將執行結果和語句保存在緩存中。
• 注意在 mysql8 后已經沒有查詢緩存這個功能了，因為這個緩存非常容易被清空掉，命中率比較低。只要對表有一個更新，這個表上的所有緩存就會被清空，因此你剛緩存下來的內容，還沒來得及用就被另一個更新給清空了。

分析器

• 既然沒有查到緩存，就需要開始執行 sql 語句了，在執行之前肯定需要先對 sql 語句進行解析。分析器主要對 sql 語句進行語法和語義分析，檢查單詞是否拼寫錯誤，還有檢查要查詢的表或字段是否存在。
• 如果分析器檢測出有錯誤就會返回類似 “You have an error in your sql” 這樣的錯誤信息，并結束查詢操作。

優化器

• 通過分析器之后，mysql 就算是理解了你要執行的操作了。通常對于同一個 sql 語句，mysql 內部可能存在多種執行方案，比如存在多個索引時，該選擇哪個索引，多個表關聯查詢時，怎么確認各個表的連接順序。
• 這些方案的執行結果都一樣，但是執行效率不一樣，所以 mysql 在執行之前需要嘗試找出一個最優的方案來，這就是優化器的主要工作。但是 mysql 也會有選擇錯誤方案的時候，這里暫不細說，留到后面再解釋原因。

執行器

• 經過優化器選定了一個方案后，執行器就按照選定的方案執行 sql 語句。前面我們有講過，在連接器中會讀取當前用戶的權限，連接器中只是獲取權限而已，并沒有對權限進行判斷和校驗。
• 所以在執行器中，在執行語句之前會判斷權限，如果沒有對應的權限則會直接返回并提示沒有相關權限。
• 這里你可能會問，為什么不在連接器中就直接判斷權限呢，這里我覺得可能是因為 mysql 要查詢的表并不一定僅限于 sql 語句中字面上的那些表，有的時候可能需要經過分析器和優化器之后才能確定到底要怎么執行，所以權限校驗放在執行器中是有道理的。
• 注意如果是在前面的查詢緩存中查到緩存之后，也會在返回結果前做權限校驗的。
• 權限校驗通過之后，就繼續打開表，調用存儲引擎提供的接口去查詢并返回結果集數據。

到這里，一條查詢 sql 語句就執行結束了。

開始

• 不知道你有沒有這種感覺，那些所謂的數據結構和算法，在日常開發工作中很少用到或者幾乎不曾用到，可能只是在每次換工作準備面試的時候才會撿起來學習學習。
• 那我希望今天這篇文章能讓你對數據結構的具體應用能有個初步的概念，就像上面說的一樣，先從我們每天都在用的 mysql 數據庫說起吧。
• 首先，mysql 主要是由 server 層和存儲層兩部分構成的。server 層主要包括連接器、查詢緩存，分析器、優化器、執行器。存儲層主要是用來存儲和查詢數據的，常用的存儲引擎有 InnoDB、MyISAM，MySQL 5.5.5 版本后使用 InnoDB 作為默認存儲引擎。
• 我們主要討論 mysql 的存儲層，不同的存儲引擎其底層的數據結構是不一樣的，我們這里就以默認的 InnoDB 為例，所以嚴格來說應該是 InnoDB 為啥要選擇 B+ 樹這種數據結構來存儲數據。

在文章正式開始之前，你先要知道 mysql 中的 InnoDB 在底層是采用 B+ 樹這種數據結構來存儲數據的。你先記住就好了，下面我們再來一步一步解釋為什么。

幾種常見的數據結構

首先你要知道，mysql 的索引主要是為了提高查詢效率的，那一定得找一個合適的數據結構來存儲數據，哈希表、數組、二叉搜索樹這三種常見的數據結構都可以提高查詢效率。

哈希表

• 哈希表就是一種以鍵值對來存儲數據的結構，你可以通過一個 key 就可以很快的查詢出對用的 value 值。哈希表主要是利用了數組的隨機訪問特性，實現思想主要是通過一個哈希函數把 key 轉換成一個哈希值，這個哈希值就對應數組中的某個下標。
• 但是由于哈希表是無序的，區間查詢效率會非常的慢，所以哈希表通常只用于查詢單個值。

有序數組

• 數組就好說了，數組具有連續性和隨機訪問特性，因此數組都能很高效的進行單個等值查詢和區間查詢，但是 mysql 不僅僅是查詢數據，還會有插入和刪除數據的操作。
• 在有序數組中插入或刪除一個數據會需要批量移動數組中其他數據，這是一個不小的消耗，影響性能。因此有序數組適合處理靜態數據，比如一些過往的不會再修改的數據。
• 在這里你可能會問，既然哈希表其實也是利用了數組的特性，那有了數組為啥還需要哈希表呢。是因為數組下標 key 只能是數字，而哈希表可以支持字符串 key，哈希函數可以把這個 key 轉換成一個數組下標。
• 同時，不同的 key 如果通過哈希函數轉換成了相同的數組下標，這就會造成沖突，在哈希表中一般會通過再拉出一個鏈表來保存這個沖突的值。

二叉搜索樹

• 注意，二叉搜索樹和二叉樹不一樣，二叉樹是指每個節點的左兒子小于父節點，父節點又小于右兒子，即二叉搜索樹的中序遍歷就是一個有序序列。
• 由于索引不僅僅是存在內存中，還會存儲在硬盤中，因此就會涉及到 IO 性能了，就要求樹的高度不能太高。實際上 B+ 樹就是通過二叉搜索樹推演改進的，我將在后面的文章再詳細解釋這個改進過程。

小結

• 哈希表適合等值查詢，由于是無序的，區間查詢會很慢。
• 有序數組適合等值和區間查詢，但是數組具有連續性，插入和刪除操作都可能需要移動其他元素。
• 二叉搜索樹由于樹的高度，區間查詢需要中序遍歷，都會導致查詢效率很慢。

• 注意，在一些文章中經常會把 B+ 樹說成 B 樹或者 B-tree，這其實是錯誤的，B 樹和 B+ 是兩種不同的樹，B+ 樹是 B 樹的一個優化，后面的文章我會再詳細解釋這個優化過程。
• 而且 B- 樹其實也就是 B 樹，這個符號并不是加減中的減號，并不是所謂的 “B 減樹”，只是一個連接符號而已。

具體的原因

索引為什么要保存在硬盤中

• 首先要明白幾個概念，服務器存儲一般分內存和硬盤，內存的大小相對于硬盤來說是很小的。內存的訪問速度是納秒級別的，非常快，而硬盤的訪問速度相對內存來說就比較慢了。
• 不管是訪問內存還是硬盤數據，操作系統都是按數據頁來讀取數據的，即每訪問一次硬盤或內存，只讀取一頁大小的數據，一頁的大小約等于 4 kb，向硬盤讀取數據的操作叫做磁盤 IO。
• 看到這里你或許會知道了 mysql 索引為啥不保存在內存中了吧，一方面是雖然內存訪問速度快但容量一般都比較小，存不了多少數據，再一個 mysql 需要讓數據持久化，如果服務器斷電或異常重啟會導致數據丟失。

怎么讓二叉搜索樹支持區間查詢

上面提到過二叉搜索樹，為了讓二叉搜索樹也支持區間查詢，我們把二叉樹的葉子節點通過一個雙向鏈表來連接，并且這個鏈表是有序的，注意葉子節點和普通節點是不一樣的

因此只需要先找到區間的起始值在鏈表中的位置，然后再往后遍歷，直到遍歷到區間的終止值，即可完成區間查詢。如下圖查找 7-30 這個區間的數據。

如何提升查詢速度

• 因為二叉搜索樹保存在硬盤中，我們每訪問一個節點，就對應著一次硬盤 IO 操作，上面有說過向硬盤讀取數據速度比較慢。因此樹的高度就代表硬盤 IO 操作的次數，所以我們要想辦法讓樹的高度變矮，來減少硬盤 IO。
• 要想樹變矮一些，那就把樹多分一些叉來吧，變成一顆多叉樹。下面分別用二叉樹和五叉樹來存儲 16 條數據，看下樹的高度又怎樣的變化。

• 根節點一般存儲在內存中，普通節點和葉子結點保存在硬盤中，因此顯然二叉樹的高度為 5，需要 5 次硬盤 IO，而五叉樹的高度為 2，查詢一個數據只需要 2 次硬盤 IO。
• 當然這僅僅是一個小數據的例子，如果有一億條數據，我們構建一個 100 叉樹，這棵樹的高度也只有 3，因此多叉樹能大大降低硬盤 IO，提升查詢速度。

那么問題又來了，對于相同的數據量，是不是構建的多叉樹的叉越多越好呢，因為叉越多樹的高度就會越矮。

上面有說過操作系是按數據頁大小來訪問硬盤的，每次 IO 只讀取一個數據頁大小的數據，如果要讀取的數據大于一個數據頁，則會導致多次 IO。因此我們要盡量讓每個節點的數據大小剛好等于一個數據頁大小，即每訪問一個節點只需一次 IO。

插入和刪除數據怎么辦

上面其實都是為了提高查詢性能的，mysql 通常還有插入和刪除操作的，這里我們再簡單說一下 B+ 樹如何處理插入和刪除節點的操作。

• 這里我們把多叉樹稱作 m 叉樹，這個 m 值是通過數據頁大小和節點數計算出來的，盡量保證每訪問一個節點就是一個數據頁的大小，而且每個節點最多只有 m 個子節點。
• 現在我們要往數據庫中插入新的數據，即要往 m 叉樹中插入新的節點，這可能就會導致某些節點的子節點個數大于 m，也就會導致該節點大小大于一個數據頁，訪問該節點就需要多次 IO。
• 為了解決這個問題，m 叉樹會把該節點分裂成兩個節點，然后改分裂操作又會導致其父節點的子節點數可能超過 m，我們再用同樣的方法分裂節點，一直影響到根節點。
• 刪除操作也是類似的思想，如果有頻繁的刪除節點，就會導致某些節點的子節點過少，就會浪費存儲空間并降低查詢效率。所以就要想辦法讓這些節點合并起來，合并的話就有可能會導致其子節點數超過 m，超過的話就再用上面的分裂方法分裂子節點。

關于節點分裂和合并操作就簡單說這些了，也不畫圖了，知道這個處理思想就好了。

下面再總結一下 B+ 樹：

• B+ 樹就是一種多叉樹，是由二叉搜索樹不斷演變過來的，為了滿足區間快速查詢，B+ 樹的葉子節點通過雙向鏈表串聯起來。
• 這里使用雙向鏈表是為了支持順序和倒序查詢，雖然雙向鏈表相對于單向鏈表雖然會浪費一倍的指針空間，但是在硬盤中這點空間幾乎微乎其微，用這點空間換時間是一件很值得的事情。
• B+ 樹的子節點數不超過 m 個，同時也不能少于 m/2 個，一旦超過就需要分裂，一旦少于就需要合并。

總結

以上是生活随笔為你收集整理的Mysql索引数据结构有多个选择，为什么一定要是B+树呢？_面试 (MySQL 索引为啥要选择 B+ 树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。