如何評價索引的好壞：
數(shù)據(jù)庫服務器有兩種存儲介質(zhì)，硬盤和內(nèi)存，為了數(shù)據(jù)安全，索引需要存放在硬盤上，這樣在硬盤上進行查詢時，就會產(chǎn)生硬盤的I/O操作，索引的查找次數(shù)也就是硬盤I/O的操作次數(shù)，所以索引需要減少硬盤的I/O操作。
- 二叉樹：
普通農(nóng)的二分查找樹，有可能退化成一條鏈表，這是查找數(shù)據(jù)的時間復雜度為 O(n)。
為此，有平衡二叉搜索樹（AVL樹， 樹堆，紅黑樹、伸展樹等）搜索時間復雜度是 O(log2n)。
對于 數(shù)據(jù)庫索引來說，O(log2n)仍然太大。
- B樹：
Balance Tree，平衡的多路搜索樹，即 每個節(jié)點不再是只有2個子節(jié)點，而是有M個子節(jié)點，它的高度遠小于平衡二叉樹的高度。
B樹的每個節(jié)點最多包含M個子節(jié)點，M成為B樹的階。每個磁盤塊中包括了關鍵字和子節(jié)點的指針。如果一個磁盤塊中包括了x 個關鍵字，那么指針數(shù)就是x + 1.對于一個100階的B樹來說，如果3層的話，最多可以存儲約100萬的索引數(shù)據(jù)。
l 根節(jié)點的兒子樹的范圍是 [2, M]
l 每個中間節(jié)點包含 k – 1個關鍵字和 k 個孩子，孩子的數(shù)量 = 關鍵字的數(shù)量 + 1, k 的取值范圍為[ceil(M/2), M]
l 葉子節(jié)點包括 k – 1 個關鍵字（葉子結點沒有孩子）。
l 每個 關鍵字 key，劃分了一個數(shù)據(jù)范圍，也就是子節(jié)點的數(shù)據(jù)范圍。
l 所有葉子節(jié)點位于同一層。
在B樹的搜索過程中，比較的次數(shù)并不少，可以把數(shù)據(jù)讀取出來，然后在內(nèi)存中比較，這樣相比于平衡二叉樹來說，磁盤I/O操作要少，在數(shù)據(jù)查詢中比平衡二叉樹效率要高。
- B+ 樹：
B+ 樹對 B樹做了改進：
l 有k個孩子的節(jié)點就有k個關鍵字，也就是孩子數(shù)量=關鍵字數(shù)量。
l 非葉子節(jié)點的關鍵字也會同時存在于子節(jié)點中，并且是在子節(jié)點中所有關鍵字的最大（或最?。?/p>
l 非葉子節(jié)點僅用于索引，不保存數(shù)據(jù)記錄，跟記錄有關的信息都放在葉子結點中，而在B樹中，非葉子節(jié)點既保存索引，也保存數(shù)據(jù)記錄。
l 所有關鍵字都在葉子節(jié)點出現(xiàn)，葉子節(jié)點構成一個有序鏈表，而且葉子節(jié)點本身按照關鍵字的大小從小到大順序鏈接。
- B 樹相對于 二叉樹，更加矮胖，可以減少查找次數(shù)（I/O次數(shù)）；
B+ 樹相對于 B樹，由于數(shù)據(jù)都在葉子節(jié)點當中，所以可以把索引一次性加載到內(nèi)存中，減少I/O次數(shù)；同時由于葉子節(jié)點是一個有序鏈表，可以加快關鍵字的范圍查詢。
