在MySql數據庫的innodb存儲引擎中，數據是按照主鍵以B+樹的形式存儲的。如果在建表的時候沒有指定主鍵，那麼引擎會自動添加一列主鍵。
B+樹
B+樹是一種平衡樹，即根節點到各個葉子節點的高度不超過1。在B+樹中，所有記錄節點都是按照鍵值的大小順序存在同一層的葉子節點上，由各個葉子節點指針進行鏈接。B+的形式如上圖所示。從上圖中，如果用戶從最左邊的葉子節點遍歷即可得到所有鍵值的順序排序：4、7、10、15、25、36、50、59、61、65、75、80、85、90。
平時我們常接觸的查找結構是平衡二叉樹或者紅黑樹。為什麼innodb存儲引擎選擇了B+樹呢？首先我們知道innodb的數據存儲磁盤上。由於磁盤IO相對於CPU和內存而言要慢很多，所以減少磁盤IO是提升性能的關鍵，另外對於機械磁盤而言順序讀取要比隨機讀取的性能高出1到2個數量級。我們來看上圖中的例子，在查找時，可以先將根節點一次讀入內存，再進行二分法查找，定位到葉子節點的位置之後，也可以一次將葉子節點加載到內存在進行查找。這樣基本上只需要2次IO就能找到數據了。對於平衡二叉樹或者紅黑樹就需要更多次的IO，並且這些IO都是離散讀，性能較差。
innodb的主鍵又被稱為聚集索引。通過聚集索引可以直接查找到整條記錄（因為B+樹的葉子節點就是數據節點，存儲了數據）。innodb還有一種輔助索引。這是一個二級索引。它也是B+樹組織的，但是葉子節點上的數據，不是數據，而是聚集索引。一個輔助索引的查找的大概過程是：在輔助索引上找到聚集索引，再通過聚集索引找到數據。可以看出相對於聚集索引，輔助索引的查找過程更長，所以一般innodb更傾向於使用聚集索引。但是也有些情況下，查找是搜索輔助索引就能完成。比如：一張表：t（a，b，c），其中a是主鍵，b是輔助索引，對於select b from t where b > 10或者select count(*) from t where b > 10都是不需要再查找聚集索引的。
我們上面提到了磁盤的順序讀的性能要明顯高於隨機讀。我們再來看輔助索引的查找過程。輔助索引也是B+樹組織的，葉子節點是按照輔助索引的值來排序的。這就導致了，如果我們按照輔助索引的順序去聚集索引查找時，是隨機讀。innodb為了提升性能，有一種優化，對於輔助索引的範圍查找，先找出這些聚集索引，再按照聚集索引進行排序，按照這個順序去聚集索引中查找，這樣可以儘量保證順序讀，並且可以充分利用緩存。
閱讀更多 java技術小碼農 的文章
