MySQL BTREE索引

個人能力有限，如有錯誤請指出，共同學(xué)習(xí)。

創(chuàng)新互聯(lián)建站堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：做網(wǎng)站、成都網(wǎng)站設(shè)計、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的盤錦網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

二叉樹

B樹

B+樹

特點：

聚簇索引

二級索引

key數(shù)據(jù)存儲量估算：

若每個頁可以存1000個key，而且樹的高度是4，那么

前提條件如下：

插入步驟

步驟一

因為索引中還沒有數(shù)據(jù)，所以此時的B+樹只有一個空的根結(jié)點，又由于一個頁只能存3個key，首先將10，20，5插入進(jìn)去（實際上此步發(fā)生了3次插入），然后在頁面內(nèi)做數(shù)據(jù)排序，最終結(jié)果如下圖：

步驟二：

由于根頁面已經(jīng)寫滿，此時插入8，將發(fā)生分裂（根頁面分裂），大致步驟如下：

注意：在分裂過程中，根結(jié)點始終是不會變的，不管變成多大的樹，根結(jié)點的頁面號始終如一。

步驟五：

插入數(shù)據(jù)40，發(fā)現(xiàn)比根結(jié)點23大，找到103號頁面，發(fā)現(xiàn)已滿，執(zhí)行分裂，分裂同上面葉子結(jié)點的分裂步驟。分裂后如圖所示：

步驟六：

繼續(xù)插入下一個數(shù)據(jù)9，因為比20小，找到101號頁面，發(fā)現(xiàn)已滿，需要做葉子結(jié)點分裂，如下圖：

傳統(tǒng)B+樹的數(shù)據(jù)刪除，一般都會有一個所謂的填充因子，來控制頁面數(shù)據(jù)的刪除比例，如果數(shù)據(jù)量小于這個填充因子所表示的數(shù)據(jù)量，就會有節(jié)點合并，這與分裂是相對應(yīng)的。

InnoDB的實現(xiàn)與傳統(tǒng)B+樹算法有不同之處，InnoDB在刪除索引數(shù)據(jù)時，會先檢查當(dāng)前頁剩余的記錄數(shù)，如果只剩下一條記錄，就會直接將這個頁面從B+樹中摘除，也只有這種情況，InnoDB才會回收一個頁面，InnoDB的頁面沒有合并一說，但是對于根節(jié)點，即使索引數(shù)據(jù)全部刪除，根節(jié)點頁依然存在，只不過是以空頁的形式存在。

下面舉個例子描述索引刪除過程，前提條件與前面插入記錄時一致。

刪除數(shù)據(jù) 50

刪除過程全部結(jié)束，最終得到一個空的索引頁。

《MySQL運維內(nèi)參》

B+樹動畫演示：

聚集索引可以用b樹實現(xiàn)么

聚集索引可以用b樹實現(xiàn)。

簡介：

B+樹中只有葉子節(jié)點會帶有指向記錄的指針，而B樹則所有節(jié)點都帶有。

B+樹索引可以分為聚集索引和非聚集索引。

mysql使用B+樹，其中Myisam是非聚集索引，innoDB是聚集索引。

聚簇索引索引的葉節(jié)點就是數(shù)據(jù)節(jié)點；而非聚簇索引的葉節(jié)點仍然是索引節(jié)點，只不過有一個指針指向?qū)?yīng)的數(shù)據(jù)塊。

B+ 樹的特點:

（1）所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中(稠密索引)，且鏈表中的關(guān)鍵字恰好是有序的。

（2）不可能在非葉子結(jié)點命中。

（3）非葉子結(jié)點相當(dāng)于是葉子結(jié)點的索引(稀疏索引)，葉子結(jié)點相當(dāng)于是存儲(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層。

MySQL索引

MySQL的Innodb存儲引擎的索引分為聚集索引和非聚集索引兩大類

特點：B+樹葉子節(jié)點存儲行數(shù)據(jù)

一個表中，必須有一個聚集索引，只能有一個聚集索引，Innodb通常把一個表的主鍵索引作為聚集索引，如果沒有主鍵InnoDB會選擇一個唯一索引代替。如果沒有這樣的索引，InnoDB會隱式的定義一個主鍵來作為聚集索引，這個字段為6個字節(jié)，類型為長整形。

利用主鍵索引查找行數(shù)據(jù)是最快的，建議使用自增主鍵原因是利于索引樹的構(gòu)建（主鍵自增寫入時新插入的數(shù)據(jù)不會影響到原有頁，插入效率高；但是如果主鍵是無序的或者隨機(jī)的，那每次的插入可能會導(dǎo)致原有頁頻繁的分裂，影響插入效率）

特點：B+樹葉子節(jié)點存儲主鍵ID

一個表中可以有多個非聚集索引，每個非聚集索引即是一棵B+樹

通過非聚集索引查找數(shù)據(jù)時，需要先在非聚集索引上找到主鍵ID，再從聚集索引獲取行數(shù)據(jù)，這個過程就稱之為回表

B樹索引中的B樹實際上是B+樹，至于為什么使用B+樹而不使用B樹或者紅黑樹的原因在另外的文章中有提及。

特點：

特點：類似JDK中的HashMap，但無法支持范圍查詢

特點：使用的算法仍然是B樹索引，不同的就是索引列的值必須唯一

對于普通索引來說，查找到滿足條件的第一個記錄后，需要查找下一個記錄，直到碰到第一個不滿足條件的記錄。

對于唯一索引來說，由于索引定義了唯一性，查找到第一個滿足條件的記錄后，就會停止繼續(xù)檢索，提升索引性能

另外插入行時會構(gòu)建該唯一索引，假如索引值重復(fù)將插入失敗，適合業(yè)務(wù)上做唯一性檢驗

通過建立倒排索引，可以極大的提升檢索效率,解決判斷字段是否包含的問題，但是業(yè)務(wù)上一般都不采用這種索引，而是使用ES處理全文搜索需求

僅對某個特定字段建立的索引，如(biz_id)

對多個字段建立的索引，如(biz_id,type)