前言

區域性原理

磁盤預讀

磁盤預讀(預讀的長度一般為頁（page）的整數倍) – 頁是存盤器的邏輯塊，作業系統往往將主存和磁盤存盤區分割為連續的大小
相等的塊，每個存盤塊稱為一頁（在許多作業系統中，頁大小通常為4k），
主存和磁盤以頁為單位交換資料，

索引是什么？

索引是幫助 MySQL 高效獲取資料的資料結構
? 索引存盤在檔案系統中
? 索引的檔案存盤形式與存盤引擎有關
? 索引檔案的結構
– 哈希表
– 二叉樹
– AVL樹（平衡二叉搜索樹）
– 紅黑樹
– B樹
– B+樹

1. MSQL為什么索引選擇B+樹？

在進一步分析為什么MySQL資料庫索引選擇使用B+樹之前
我相信很多小伙伴對資料結構中的樹還是有些許模糊的
因此我們由淺入深一步步探討樹的演程序序
再一步步引出B樹以及為什么MySQL資料庫索引選擇使用B+樹！

學過資料結構的一般對最基礎的樹都有所認識，因此我們就從與我們主題更為相近的二叉查找樹開始，

1.1 哈希表hash

簡介：

哈希表是一種根據關鍵碼去尋找值的資料映射結構，該結構通過把關鍵碼映射的位置去尋找存放值的地方
如果我想要獲取“按”字詳細資訊，我肯定會去根據拼音an去查找 拼音索引（當然也可以是偏旁索引）
我們首先去查an在字典的位置，查了一下得到“安”，結果如下，
這程序就是鍵碼映射，在公式里面，就是通過key去查找f(key)，其中，按就是關鍵字（key），f（）就是字典索引，也就是哈希函式
查到的頁碼4就是哈希值，

局限性：

哈希表可以完成索引的存盤，每次在添加索引的時候需要計算指定列的hash值，取橫運算后計算出下標，將元素插入下標位置即可
適合場景：
等值查詢
表中的資料是無序資料（范圍查找的時候比較浪費時間，需要挨個進行遍歷操作)
在企業中多數的查詢時是范圍查詢而不是等值查詢
所以此時hash表不合適范圍查詢
hash表在使用的時候，需要將全部的資料加載到記憶體，比較耗費記憶體的空間，也不是很合適
如果我們要查的是“按”，而不是“安，但是他們的拼音都是一樣的，也就是通過關鍵字按和關鍵字安可以映射到一樣的字典頁碼4的位置
這就是哈希沖突（也叫哈希碰撞）

1.2 二叉樹

簡介：

二叉查找樹也稱為有序二叉查找樹，滿足二叉查找樹的一般性質，是指一棵空樹具有如下性質：


1、任意節點左子樹不為空,則左子樹的值均小于根節點的值；
2、任意節點右子樹不為空,則右子樹的值均大于于根節點的值；
3、任意節點的左右子樹也分別是二叉查找樹；
4、沒有鍵值相等的節點；

上圖為一個普通的二叉查找樹，按照中序遍歷的方式可以從小到大的順序排序輸出：2、3、5、6、7、8，
對上述二叉樹進行查找，如查鍵值為5的記錄，先找到根，其鍵值是6，6大于5，因此查找6的左子樹找到3；
而5大于3，再找其右子樹；一共找了3次，如果按2、3、5、6、7、8的順序來找同樣需求3次，
用同樣的方法在查找鍵值為8的這個記錄，這次用了3次查找，而順序查找需要6次，
計算平均查找次數得：
順序查找的平均查找次數為（1+2+3+4+5+6）/ 6 = 3.3次，
二叉查找樹的平均查找次數為（3+3+3+2+2+1）/6=2.3次，
二叉查找樹的平均查找速度比順序查找來得更快，

局限性：

一個二叉查找樹是由n個節點隨機構成，所以，對于某些情況，二叉查找樹會退化成一個有n個節點的線性鏈，
大家看上圖，如果我們的根節點選擇是最小或者最大的數，那么二叉查找樹就完全退化成了線性結構，
上圖中的平均查找次數為（1+2+3+4+5+5）/6=3.16次，和順序查找差不多，顯然這個二叉樹的查詢效率就很低
因此若想最大性能的構造一個二叉查找樹，需要這個二叉樹是平衡的
（這里的平衡從一個顯著的特點可以看出這一棵樹的高度比上一個輸的高度要大，在相同節點的情況下也就是不平衡）
從而引出了一個新的定義- 平衡二叉樹AVL，

1.3 AVL樹

簡介：

AVL樹是帶有平衡條件的二叉查找樹，一般是用平衡因子差值判斷是否平衡并通過旋轉來實作平衡，左右子樹樹高不超過1，
和紅黑樹相比，它是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1），
不管我們是執行插入還是洗掉操作，只要不滿足上面的條件，就要通過1到N次的旋轉來保持平衡，
而旋轉是非常耗時的，嚴重影響插入的性能，由此我們可以知道AVL樹適合用于插入洗掉次數比較少，但查找多的情況，
上圖是一個普通的平衡二叉樹，這張圖我們可以看出，任意節點的左右子樹的平衡因子差值都不會大于1，

局限性：

AVL樹是一顆嚴格意義上的平衡樹，最高子樹跟最低子樹高度之差不能超過1，
因此在進行元素插入的時候，會進行1到N次的旋轉，而旋轉嚴重影響插入的性能，
當然，如果應用場景中對插入洗掉不頻繁，只是對查找要求較高，那么AVL還是較優于紅黑樹，

1.4 紅黑樹

簡介：

紅黑樹是基于AVL樹的一個升級，損失了部分查詢的性能，來提升插入的性能，在紅黑樹中最低子樹跟最高子樹之差小于2倍即可，
在插入的時候，不需要進行N多次的旋轉操作，而且還加入了變色的特性，來滿足插入和查詢性能的平衡，
它是一種二叉查找樹，但在每個節點增加一個存盤位表示節點的顏色，可以是red或black，
通過對任何一條從根到葉子的路徑上各個節點著色的方式的限制，紅黑樹確保沒有一條路徑會比其它路徑長出兩倍，
它是一種弱平衡二叉樹(由于是若平衡，可以推出，相同的節點情況下，AVL樹的高度低于紅黑樹)，
相對于要求嚴格的AVL樹來說，它的旋轉次數變少，所以對于搜索、插入、洗掉操作多的情況下，我們就用紅黑樹，
但樹的深度無法控制，插入教據的性能還是不夠完美，

性質：

1、每個節點非紅即黑；
2、根節點是黑的；
3、每個葉節點(葉節點即樹尾端NULL指標或NULL節點)都是黑的；
4、如果一個節點是紅的,那么它的兩兒子都是黑的；
5、對于任意節點而言，其到葉子點樹NULL指標的每條路徑都包含相同數目的黑節點；
6、每條路徑都包含相同的黑節點；

應用

1、廣泛用于C++的STL中，Map和Set都是用紅黑樹實作的；
2、著名的Linux行程調度Completely Fair Scheduler，用紅黑樹管理行程控制塊，行程的虛擬記憶體區域都存盤在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指標指向相鄰的地址虛擬存盤區域，右指標指向相鄰的高地址虛擬地址空間；
3、IO多路復用epoll的實作采用紅黑樹組織管理sockfd，以支持快速的增刪改查；
4、Nginx中用紅黑樹管理timer，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中TreeMap的實作；

1.5 總結

上述的哈希表與三種樹（二叉查找樹、AVL和紅黑樹）
相信大家已經知道了MySQL為什么要使用B+樹作為索引的實作了叭
哈希表，二叉樹及其N多的變種都不能支撐索引，原因是樹的深度無法控制（深度過深而造成io次數變多）或者插入資料的性能比較低
解決辦法：多叉樹

2. B樹/B+樹

2.1 B樹特點：

1、所有鍵值分布在整顆樹中
2、搜索有可能在非葉子結點結束，在關鍵字全集內做一次查找,性能逼近二分查找
3、每個節點最多擁有m個子樹
4、根節點至少有2個子樹
5、分支節點至少擁有m/2顆子樹（除根節點和葉子節點外都是分支節點）
6、所有葉子節點都在同一層、每個節點最多可以有m-1個key，并且以升序排列

局限性：

實體圖說明：
每個節點占用一個磁盤塊（每個假設4k），一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指標，指標存盤的是子節點所在磁盤塊的地址，兩個關鍵詞劃分成的三個范圍域對應三個指標指向的子樹的資料的范圍域，以根節點為例，關鍵字為 16 和 34，P1 指標指向的子樹的資料范圍為小于 16，P2 指標指向的子樹的資料范圍為 16~34，P3 指標指向的子樹的資料范圍為大于 34，
查找關鍵字程序：
1、根據根節點找到磁盤塊 1，讀入記憶體，【磁盤 I/O 操作第 1 次】
2、比較關鍵字 28 在區間（16,34），找到磁盤塊 1 的指標 P2，
3、根據 P2 指標找到磁盤塊 3，讀入記憶體，【磁盤 I/O 操作第 2 次】
4、比較關鍵字 28 在區間（25,31），找到磁盤塊 3 的指標 P2，
5、根據 P2 指標找到磁盤塊 8，讀入記憶體，【磁盤 I/O 操作第 3 次】
6、在磁盤塊 8 中的關鍵字串列中找到關鍵字 28，
缺點：

1、每個節點都有key，同時也包含data，而每個頁存盤空間是有限的，如果data比較大的話會導致每個節點存盤的key數量變小
2、當存盤的資料量很大的時候會導致深度較大，增大查詢時磁盤io次數，進而影響查詢性能

2.2 mysql索引資料結構 – B+樹

B+Tree是在BTree的基礎之上做的一種優化，變化如下：
1、B+Tree每個節點可以包含更多的節點，這個做的原因有兩個:
第一個原因是為了降低樹的高度，
第二個原因是將資料范圍變為多個區間，區間越多，資料檢索越快
2、非葉子節點存盤key，葉子節點存盤key和資料
3、葉子節點兩兩指標相互連接（符合磁盤的預讀特性），順序查詢性能更高

注意：在B+Tree上有兩個頭指標，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有葉子節點（即資料節點）之間是一種鏈式環結構，因此可以對 B+Tree 進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找，另一種是從根節點開始，進行隨機查找，

下一篇：有InnoDB和MyISAM兩種引擎，對B+樹資料增刪改的詳細介紹