索引是單獨的，物理的對數據庫表中一列或多列的值進行排序的一種存儲結構，讓程序能夠快速找到所需內容。
索引是一種數據結構（平衡樹非二叉），即B樹，B+樹，通過不斷的縮小想要獲得數據的範圍來篩選出最終想要的結果，同時把隨機的事件變成順序的事件。
B樹：
1.定義任意非葉子結點最多隻有M個兒子；且M>2；
2.根結點的兒子數為[2, M]；
3.除根結點以外的非葉子結點的兒子數為[M/2, M]；
4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小於K[1]的
子樹，P[M]指向關鍵字大於K[M-1]的子樹，其它P[i]指向關鍵字屬於(K[i-1], K[i])的子樹；
8.所有葉子結點位於同一層；
B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果
命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複，直到所對應的兒子指針為
空，或已經是葉子結點；
B-樹的特性：
1.關鍵字集合分佈在整顆樹中；
2.任何一個關鍵字出現且只出現在一個結點中；
3.搜索有可能在非葉子結點結束；
4.其搜索性能等價於在關鍵字全集內做一次二分查找；
5.自動層次控制；
由於限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少
利用率，其最底搜索性能為：
其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；
所以B-樹的性能總是等價於二分查找（與M值無關），也就沒有B樹平衡的問題；
由於M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各佔
M/2的結點；刪除結點時，需將兩個不足M/2的兄弟結點合併；
B+樹是B-樹的變體，也是一種多路搜索樹：
1.其定義基本與B-樹同，除了：
2.非葉子結點的子樹指針與關鍵字個數相同；
3.非葉子結點的子樹指針P[i]，指向關鍵字值屬於[K[i], K[i+1])的子樹
（B-樹是開區間）；
5.為所有葉子結點增加一個鏈指針；
6.所有關鍵字都在葉子結點出現；
B+的特性：
1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好
是有序的；
2.不可能在非葉子結點命中；
3.非葉子結點相當於是葉子結點的索引（稀疏索引），葉子結點相當於是存儲
（關鍵字）數據的數據層；
4.更適合文件索引系統；
