[MySQL]B+樹索引_MySQL

[MySQL]B+樹索引

B+樹是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，由平衡樹和二叉查找樹結(jié)合產(chǎn)生，它是為磁盤或其它直接存取輔助設(shè)備而設(shè)計(jì)的一種平衡查找樹，在B+樹中，所有的記錄節(jié)點(diǎn)都是按鍵值大小順序存放在同一層的葉節(jié)點(diǎn)中，葉節(jié)點(diǎn)間用指針相連，構(gòu)成雙向循環(huán)鏈表，非葉節(jié)點(diǎn)（根節(jié)點(diǎn)、枝節(jié)點(diǎn)）只存放鍵值，不存放實(shí)際數(shù)據(jù)。下面看一個(gè)2層B+樹的例子：

保持樹平衡主要是為了提高查詢性能，但為了維護(hù)樹的平衡，成本也是巨大的，當(dāng)有數(shù)據(jù)插入或刪除時(shí)，需采用拆分節(jié)點(diǎn)、左旋、右旋等方法。B+樹因?yàn)槠涓呱瘸鲂?，所以具有高平衡性，通常其高度都?~3層，查詢時(shí)可以有效減少IO次數(shù)。B+樹索引可以分為聚集索引(clustered index)和非聚集索引（即輔助索引，secondary index）。

聚集索引

InnoDB表時(shí)索引組織表，即表中數(shù)據(jù)按主鍵B+樹存放，葉子節(jié)點(diǎn)直接存放數(shù)據(jù)，每張表只能有一個(gè)聚集索引。

輔助索引

輔助索引（也稱非聚集索引）是指葉節(jié)點(diǎn)不包含行的全部數(shù)據(jù)，葉節(jié)點(diǎn)除了包含鍵值之外，還包含一個(gè)書簽連接，通過該書簽再去找相應(yīng)的行數(shù)據(jù)。下圖顯示了InnoDB存儲(chǔ)引擎輔助索引和聚集索引的關(guān)系：

從上圖中可以看出，輔助索引葉節(jié)點(diǎn)存放的是主鍵值，獲得主鍵值后，再從聚集索引中查找整行數(shù)據(jù)。舉個(gè)例子，如果在一顆高度為3的輔助索引中查找數(shù)據(jù)，首先從輔助索引中獲得主鍵值（3次IO），接著從高度為3的聚集索引中查找以獲得整行數(shù)據(jù)（3次IO），總共需6次IO。一個(gè)表上可以存在多個(gè)輔助索引。

索引組織表 VS 堆表

MyISAM中的表是以堆表的方式進(jìn)行存儲(chǔ)，堆表沒有主鍵，因此沒有聚集索引，輔助索引葉節(jié)點(diǎn)不是返回主鍵值，而是返回行標(biāo)志符（ROWID），通過ROWID再去查找相應(yīng)的行。

很顯然，對(duì)于堆表來說，通過輔助索引訪問更快(IO更少)，但是如果在OLTP應(yīng)用下，表中數(shù)據(jù)經(jīng)常被修改，輔助索引中的ROWID可能需要經(jīng)常更新，如果更新影響到物理地址的更改，這種開銷比索引組織表要大得多。

因此，索引組織表還是堆表，這取決于你的應(yīng)用，如果你的應(yīng)用是OLAP，數(shù)據(jù)更新很少，堆表更好一些。

復(fù)合索引

復(fù)合索引是指對(duì)表上的多個(gè)列做索引，下面是一個(gè)復(fù)合索引的例子：

[sql]

alter table t add key idx_a_b(a,b);

下圖是B+樹結(jié)構(gòu)：

很顯然，對(duì)于where a = xxx and b=xxx 這樣的語句是可以使用這個(gè)復(fù)合索引的。現(xiàn)在看看對(duì)單個(gè)列的情況，where a = xxx也是可以使用該復(fù)合索引，因?yàn)閍列在復(fù)合索引中也是有序的，但對(duì)于where b =xxx 這樣的語句是無法使用該復(fù)合索引，因?yàn)樗菬o序的。

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com