[MySQL]B+樹索引
B+樹是一種經典的數據結構，由平衡樹和二叉查找樹結合產生，它是為磁盤或其它直接存取輔助設備而設計的一種平衡查找樹，在B+樹中，所有的記錄節點都是按鍵值大小順序存放在同一層的葉節點中，葉節點間用指針相連，構成雙向循環鏈表，非葉節點（根節點、枝節點）只存放鍵值，不存放實際數據。下面看一個2層B+樹的例子：
保持樹平衡主要是為了提高查詢性能，但為了維護樹的平衡，成本也是巨大的，當有數據插入或刪除時，需采用拆分節點、左旋、右旋等方法。B+樹因為其高扇出性，所以具有高平衡性，通常其高度都在2~3層，查詢時可以有效減少IO次數。B+樹索引可以分為聚集索引(clustered index)和非聚集索引（即輔助索引，secondary index）。
聚集索引
InnoDB表時索引組織表，即表中數據按主鍵B+樹存放，葉子節點直接存放數據，每張表只能有一個聚集索引。
輔助索引
輔助索引（也稱非聚集索引）是指葉節點不包含行的全部數據，葉節點除了包含鍵值之外，還包含一個書簽連接，通過該書簽再去找相應的行數據。下圖顯示了InnoDB存儲引擎輔助索引和聚集索引的關系：
從上圖中可以看出，輔助索引葉節點存放的是主鍵值，獲得主鍵值後，再從聚集索引中查找整行數據。舉個例子，如果在一顆高度為3的輔助索引中查找數據，首先從輔助索引中獲得主鍵值（3次IO），接著從高度為3的聚集索引中查找以獲得整行數據（3次IO），總共需6次IO。一個表上可以存在多個輔助索引。
索引組織表 VS 堆表
MyISAM中的表是以堆表的方式進行存儲，堆表沒有主鍵，因此沒有聚集索引，輔助索引葉節點不是返回主鍵值，而是返回行標志符（ROWID），通過ROWID再去查找相應的行。
很顯然，對於堆表來說，通過輔助索引訪問更快(IO更少)，但是如果在OLTP應用下，表中數據經常被修改，輔助索引中的ROWID可能需要經常更新，如果更新影響到物理地址的更改，這種開銷比索引組織表要大得多。
因此，索引組織表還是堆表，這取決於你的應用，如果你的應用是OLAP，數據更新很少，堆表更好一些。
復合索引
復合索引是指對表上的多個列做索引，下面是一個復合索引的例子：
[sql]
alter table t add key idx_a_b(a,b);
下圖是B+樹結構：
很顯然，對於where a = xxx and b=xxx 這樣的語句是可以使用這個復合索引的。現在看看對單個列的情況，where a = xxx也是可以使用該復合索引，因為a列在復合索引中也是有序的，但對於where b =xxx 這樣的語句是無法使用該復合索引，因為它是無序的。
