索引是什麼
比較抽象，舉一個例子，平時看任何一本書，首先看到的都是目錄，通過目錄去查詢書籍裡面的內容會非常的迅速。
上圖就是一本金瓶梅的書，書籍的目錄是按順序放置的，有第一節，第二節它本身就是一種順序存放的數據結構，是一種順序結構。
另外通過目錄（索引），可以快速查詢到目錄裡面的內容，它能高效獲取數據，通過這個簡單的案例可以理解所以就是高效獲取數據的數據結構
再來看一個發雜的情況，
我們要去圖書館找一本書，這圖書館的書肯定不是線性存放的，它對不同的書籍內容進行了分類存放，整索引由於一個個節點組成，根節點有中間節點，中間節點下面又由子節點，最後一層是葉子節點，
可見，整個索引結構是一棵倒掛著的樹，其實它就是一種數據結構，這種數據結構比前面講到的線性目錄更好的增加了查詢的速度。
MySql中的索引
MySql中的索引其實也是這麼一回事，我們可以在數據庫中建立一系列的索引，比如創建主鍵的時候默認會創建主鍵索引，上圖是一種BTREE的索引。每一個節點都是主鍵的ID
當我們通過ID來查詢內容的時候，首先去查索引庫，在到索引庫後能快速的定位索引的具體位置。
談下B+Tree
要談B+TREE說白了還是Tree,但談這些之前還要從基礎開始講起
二分查找
二分查找法（binary search） 也稱為折半查找法，用來查找一組有序的記錄數組中的某一記錄。
其基本思想是：將記錄按有序化（遞增或遞減）排列，在查找過程中採用跳躍式方式查找，即先以有序數列的中點位置作為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區間縮小一半。
# 給出一個例子，注意該例子已經是升序排序的，且查找 數字 48
數據：5， 10， 19， 21， 31， 37， 42， 48， 50， 52
下標：0， 1， 2， 3， 4， 5， 6， 7， 8， 9
• 步驟一：設 low 為下標最小值 0 ， high 為下標最大值 9 ;
• 步驟二：通過 low 和 high 得到 mid ，mid=（low + high） / 2，初始時 mid 為下標 4 (也可以=5，看具體算法實現)；
• 步驟三 ： mid=4 對應的數據值是31，31 < 48（我們要找的數字）；
• 步驟四：通過二分查找的思路，將 low 設置為31對應的下標 4 ， high 保持不變為 9 ，此時 mid 為 6 ；
• 步驟五 ： mid=6 對應的數據值是42，42 < 48（我們要找的數字）；
• 步驟六：通過二分查找的思路，將 low 設置為42對應的下標 6 ， high 保持不變為 9 ，此時 mid 為 7 ；
• 步驟七 ： mid=7 對應的數據值是48，48 == 48（我們要找的數字），查找結束；
通過3次 二分查找 就找到了我們所要的數字，而順序查找需8
二叉樹(Binary Tree)
每個節點至多隻有二棵子樹；
• 二叉樹的子樹有左右之分，次序不能顛倒；2x -1• 一棵深度為k，且有 個節點，稱為滿二叉樹(Full Tree)；
• 一棵深度為k，且root到k-1層的節點樹都達到最大，第k層的所有節點都 連續集中 在最左邊，此時為完全二叉樹（Complete Tree）
平衡二叉樹（AVL-樹）
l 左子樹和右子樹都是平衡二叉樹；
l 左子樹和右子樹的高度差絕對值不超過1；
◦ 平衡二叉樹
◦ 非平衡二叉樹
平衡二叉樹的遍歷
l 前序 ：6 ,3, 2, 5,7, 8（ROOT節點在開頭, 中 -左-右 順序）
l 中序 ：2, 3, 5, 6,7, 8（中序遍歷即為升序，左- 中 -右 順序）
l 後序 ：2, 5, 3, 8,7, 6 （ROOT節點在結尾，左-右- 中 順序）
平衡二叉樹的旋轉
需要通過旋轉（左旋，右旋）來維護平衡二叉樹的平衡，在添加和刪除的時候需要有額外的開銷。
B+樹
B+樹的定義
l 數據只存儲在葉子節點上，非葉子節點只保存索引信息；
◦ 非葉子節點（索引節點）存儲的只是一個Flag，不保存實際數據記錄；
◦ 索引節點指示該節點的左子樹比這個Flag小，而右子樹大於等於這個Flag
l 葉子節點本身按照數據的升序排序進行鏈接(串聯起來)；
◦ 葉子節點中的數據在 物理存儲上是無序 的，僅僅是在 邏輯上有序 （通過指針串在一起）；
B+樹的作用
l 在塊設備上，通過B+樹可以有效的存儲數據；
l 所有記錄都存儲在葉子節點上，非葉子(non-leaf)存儲索引(keys)信息；
l B+樹含有非常高的扇出（fanout），通常超過100，在查找一個記錄時，可以有效的減少IO操作；
B+樹的扇出(fan out)
n 該 B+ 樹高度為 2
n 每葉子頁（LeafPage）4條記錄
n 扇出數為5
n 葉子節點(LeafPage)由小到大（有序）串聯在一起
扇出 是每個索引節點(Non-LeafPage)****指向每個葉子節點****(LeafPage)的指針
扇出數 = 索引節點(Non-LeafPage)可存儲的最大關鍵字個數 + 1
圖例中的索引節點(Non-LeafPage)最大可以存放4個關鍵字，但實際使用了3個；
閱讀更多 享學課堂online 的文章
