mysql數據庫支持多種索引，例如b樹索引、哈希索引、全文索引等，本文著重講解下b樹索引。（推薦：《mysql教程》）
索引原理&本質
MySQL官方解釋：索引是為MySQL提高獲取數據效率的數據結構，為了快速查詢數據。索引是滿足某種特定查找算法的數據結構，而這些數據結構會以某種方式指向數據，從而實現高效查找數據。
B+樹
MySQL一般以B+樹作為其索引結構，那么B+樹有什么特點呢？
樹度為n的話，每個節點指針上限為2n+1
非葉子節點不存儲數據，只存儲指針索引；葉子節點存儲所有數據，不存儲指針
在經典B+樹基礎上增加了順序訪問指針，每個葉子節點都有指向相鄰下一個葉子節點的指針，如圖所示。主要為了提高區間訪問的性能，例如要找key為20到50的所有數據，只要按著順序訪問路線一次性訪問所有數據節點。
帶順序訪問的B+樹簡圖
局部性原理和磁盤預讀
那么為什么數據庫系統普遍使用B+樹作為索引結構，而不選例如紅黑樹其他結構呢？
首先要先來介紹下局部性原理和磁盤預讀的概念。
一般來說，索引本身較大，不會全部存儲在內存中，會以索引文件的形式存儲在磁盤上。所以索引查找數據過程中就會產生磁盤IO操作，而磁盤IO相對于內存存取非常緩慢，因此索引結構要盡量減少磁盤IO的存取次數。
為了減少磁盤IO，磁盤往往會進行數據預讀，會從某位置開始，預先向后讀取一定長度的數據放入內存，即局部性原理。因為磁盤順序讀取的效率較高，不需要尋道時間，因此可以提高IO效率。
預讀長度一般為頁的整數倍，主存和磁盤以頁作為單位交換數據。當需要讀取的數據不在內存時，觸發缺頁中斷，系統會向磁盤發出讀取磁盤數據的請求，磁盤找到數據的起始位置并向后連續讀取一頁或幾頁數據載入內存，然后中斷返回，系統繼續運行。而一般數據庫系統設計時會將B+樹節點的大小設置為一頁，這樣每個節點的載入只需要一次IO。
