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