聚簇索引與非聚簇索引

不同的存儲(chǔ)引擎,數(shù)據(jù)文件和索引文件位置是不同的,但是都是在磁盤上而不是內(nèi)存上,根據(jù)索引文件、數(shù)據(jù)文件是否放在一起而有了分類:

聚簇索引:數(shù)據(jù)文件和索引文件放在一起,例如:innodb。

每一個(gè)數(shù)據(jù)庫在磁盤上都會(huì)有一個(gè)對(duì)應(yīng)的文件:

進(jìn)去其中一個(gè)文件夾:

這其中:

• frm:存儲(chǔ)的是表結(jié)構(gòu)。
• ibd:存儲(chǔ)數(shù)據(jù)文件和索引文件。

注意:mysql的innodb默認(rèn)會(huì)將數(shù)據(jù)文件以及索引文件放在表格空間中,不會(huì)為每一個(gè)單獨(dú)的表保存一份數(shù)據(jù)文件,如果需要單獨(dú)保存,那么要將 innodb_file_per_table 設(shè)置為on。

非聚簇索引:數(shù)據(jù)和索引文件各自分開存放,例如:MyISAM

• frm 存儲(chǔ)表結(jié)構(gòu)。
• MYI存儲(chǔ)索引數(shù)據(jù)。
• MYD 存儲(chǔ)實(shí)際數(shù)據(jù)。

索引備選存儲(chǔ)結(jié)構(gòu)

• 哈希表。
• 二叉樹。
• B樹。
• B+樹。

HashMap(散列表)

哈希表可以完成索引的存儲(chǔ),每次添加索引需要計(jì)算指定列的hash值,取模運(yùn)算后計(jì)算出下標(biāo),將元素插入下標(biāo)位,使用場(chǎng)景:等值查詢,但是表格中的數(shù)據(jù)是無序數(shù)據(jù)(范圍查找比較消耗時(shí)間,需要進(jìn)行遍歷操作),在企業(yè)中查詢更多是范圍查詢,不合適.另外,Hashmap作為索引的時(shí)候,需要全部加載到內(nèi)存,消耗內(nèi)存空間。于是考慮樹結(jié)構(gòu).

HashMap索引的限制:

• 哈希索引只包含哈希值和行指針，而不存儲(chǔ)字段值，所以不能使用索引中的值來避免讀取行。
• 哈希索引數(shù)據(jù)并不是按照索引值順序存儲(chǔ)的，所以也就無法用于排序。
• 哈希索引也不支持部分索引列匹配查找，因?yàn)楣Ｋ饕冀K是使用索引列的全部內(nèi)容來計(jì)算哈希值的。
• 哈希索引只支持等值比較查詢，包括=、IN()、<>(注意<>和<=>是不同的操作)。也不支持任何范圍查詢，例如WHERE price>100。
• 訪問哈希索引的數(shù)據(jù)非?？?，除非有很多哈希沖突(不同的索引列值卻有相同的哈希值)。當(dāng)出現(xiàn)哈希沖突的時(shí)候，存儲(chǔ)引擎必須遍歷鏈表中所有的行指針，逐行進(jìn)行比較，直到找到所有符合條件的行。
• 如果哈希沖突很多的話，一些索引維護(hù)操作的代價(jià)也會(huì)很高。例如，如果在某個(gè)選擇性很低(哈希沖突很多)的列上建立哈希索引，那么當(dāng)從表中刪除一行時(shí)，存儲(chǔ)引擎需要遍歷對(duì)應(yīng)哈希值的鏈表中的每一行，找到并刪除對(duì)應(yīng)行的引用，沖突越多，代價(jià)越大。

樹的發(fā)展緣由

計(jì)算機(jī)領(lǐng)域的樹的特點(diǎn)是左子樹小于根節(jié)點(diǎn),右子樹大于根節(jié)點(diǎn),從左到右是有序的,多叉樹查找效率比較低,后來有了二叉樹,二叉樹接近二分查找(時(shí)間復(fù)雜度),但是會(huì)出現(xiàn)下面這種情況,變成了查詢時(shí)間復(fù)雜度高的鏈表查詢:

于是有了 平衡樹(AVL樹,要求左右結(jié)點(diǎn)高度差不大于于1),也就是插入數(shù)據(jù)之后,會(huì)自旋調(diào)整變成平衡樹,但是旋轉(zhuǎn)會(huì)影響插入的性能,也就是如果查詢多但是插入少的話可以用AVL樹,但是插入多的話就不適合,為了優(yōu)化插入的時(shí)間復(fù)雜度,產(chǎn)生了紅黑樹,紅黑樹左右子節(jié)點(diǎn)高度差不超過一倍即可(例如左子樹高度4,那么右子樹高度可以是8),但是紅黑樹問題是:由于允許子樹高度差超過一倍,可能出現(xiàn)由于樹的深度過大而造成磁盤IO讀寫過于頻繁，進(jìn)而導(dǎo)致效率低下的情況。

為什么會(huì)出現(xiàn)這樣的情況，我們知道要獲取磁盤上數(shù)據(jù)，必須先通過磁盤移動(dòng)臂移動(dòng)到數(shù)據(jù)所在的柱面，然后找到指定盤面，接著旋轉(zhuǎn)盤面找到數(shù)據(jù)所在的磁道，最后對(duì)數(shù)據(jù)進(jìn)行讀寫。磁盤IO代價(jià)主要花費(fèi)在查找所需的柱面上，樹的深度過大會(huì)造成磁盤IO頻繁讀寫。根據(jù)磁盤查找存取的次數(shù)往往由樹的高度所決定，所以，只要我們通過某種較好的樹結(jié)構(gòu)減少樹的結(jié)構(gòu)盡量減少樹的高度，B樹可以有多個(gè)子女，從幾十到上千，可以降低樹的高度。

接下來考慮B樹(B-樹)。

B樹

B樹特點(diǎn)是,結(jié)點(diǎn)(非葉子結(jié)點(diǎn))有可變數(shù)量的子節(jié)點(diǎn)(事先設(shè)定好),在一個(gè)節(jié)點(diǎn)中需要設(shè)置鍵值,因?yàn)樽庸?jié)點(diǎn)數(shù)量有一定的允許范圍，所以B樹不需要像其他自平衡查找樹那樣頻繁地重新保持平衡,B樹示意圖:

B樹特點(diǎn)：

1、所有鍵值分布在整顆樹中。

2、搜索有可能在非葉子結(jié)點(diǎn)結(jié)束，在關(guān)鍵字全集內(nèi)做一次查找,性能逼近二分查找。

3、每個(gè)節(jié)點(diǎn)最多擁有m個(gè)子樹,最多有m-1個(gè)鍵值。

4、根節(jié)點(diǎn)至少有2個(gè)子樹。

5、分支節(jié)點(diǎn)至少擁有m/2顆子樹(除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外都是分支節(jié)點(diǎn))。

6、所有葉子節(jié)點(diǎn)都在同一層、每個(gè)節(jié)點(diǎn)最多可以有m-1個(gè)key，并且以升序排列。

B樹鍵值攜帶數(shù)據(jù)

實(shí)例圖說明：

每個(gè)節(jié)點(diǎn)占用一個(gè)磁盤塊，一個(gè)節(jié)點(diǎn)上有兩個(gè)升序排序的關(guān)鍵字和三個(gè)指向子樹根節(jié)點(diǎn)的指針，指針存儲(chǔ)的是子節(jié)點(diǎn)所在磁盤塊的地址。兩個(gè)關(guān)鍵詞劃分成的三個(gè)范圍域?qū)?yīng)三個(gè)指針指向的子樹的數(shù)據(jù)的范圍域。以根節(jié)點(diǎn)為例，關(guān)鍵字為 16 和 34，P1 指針指向的子樹的數(shù)據(jù)范圍為小于 16，P2 指針指向的子樹的數(shù)據(jù)范圍為 16~34，P3 指針指向的子樹的數(shù)據(jù)范圍為大于 34。

查找關(guān)鍵字過程：

1、根據(jù)根節(jié)點(diǎn)找到磁盤塊 1，讀入內(nèi)存?！敬疟P I/O 操作第 1 次】。

2、比較關(guān)鍵字 28 在區(qū)間(16,34)，找到磁盤塊 1 的指針 P2。

3、根據(jù) P2 指針找到磁盤塊 3，讀入內(nèi)存?！敬疟P I/O 操作第 2 次】。

4、比較關(guān)鍵字 28 在區(qū)間(25,31)，找到磁盤塊 3 的指針 P2。

5、根據(jù) P2 指針找到磁盤塊 8，讀入內(nèi)存?！敬疟P I/O 操作第 3 次】。

6、在磁盤塊 8 中的關(guān)鍵字列表中找到關(guān)鍵字 28。

缺點(diǎn)：

1、每個(gè)節(jié)點(diǎn)都有key，同時(shí)也包含data，而每個(gè)頁存儲(chǔ)空間是有限的，如果data比較大的話會(huì)導(dǎo)致每個(gè)節(jié)點(diǎn)存儲(chǔ)的key數(shù)量變小

2、當(dāng)存儲(chǔ)的數(shù)據(jù)量很大的時(shí)候會(huì)導(dǎo)致深度較大，增大查詢時(shí)磁盤io次數(shù)，進(jìn)而影響查詢性能

B+樹

特點(diǎn):

B+樹與B樹類似,但只有葉節(jié)點(diǎn)存放數(shù)據(jù)，其余節(jié)點(diǎn)用來索引,B-樹是每個(gè)索引節(jié)點(diǎn)都會(huì)有Data域.B-樹/B+樹的特點(diǎn)就是每層節(jié)點(diǎn)數(shù)目非常多，層數(shù)很少，目的就是為了就少磁盤IO次數(shù)，B-樹的每個(gè)節(jié)點(diǎn)都有data域(指針)，這無疑增大了節(jié)點(diǎn)大小，說白了增加了磁盤IO次數(shù)(磁盤IO一次讀出的數(shù)據(jù)量大小是固定的，單個(gè)數(shù)據(jù)變大，每次讀出的就少，IO次數(shù)增多，一次IO多耗時(shí))，而B+樹除了葉子節(jié)點(diǎn)其它節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)，節(jié)點(diǎn)小，磁盤IO次數(shù)就少。這是優(yōu)點(diǎn)之一。

另一個(gè)優(yōu)點(diǎn)是： B+樹所有的Data域在葉子節(jié)點(diǎn)，一般來說都會(huì)進(jìn)行一個(gè)優(yōu)化，就是將所有的葉子節(jié)點(diǎn)用指針串起來。這樣遍歷葉子節(jié)點(diǎn)就能獲得全部數(shù)據(jù)，這樣就能進(jìn)行區(qū)間訪問啦。在數(shù)據(jù)庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的遍歷操作。

圖示:

B+Tree是在BTree的基礎(chǔ)之上做的一種優(yōu)化，變化如下：

1、B+Tree每個(gè)節(jié)點(diǎn)可以包含更多的節(jié)點(diǎn)，這個(gè)做的原因有兩個(gè)，第一個(gè)原因是為了降低樹的高度，第二個(gè)原因是將數(shù)據(jù)范圍變?yōu)槎鄠€(gè)區(qū)間，區(qū)間越多，數(shù)據(jù)檢索越快

2、非葉子節(jié)點(diǎn)存儲(chǔ)key，葉子節(jié)點(diǎn)存儲(chǔ)key和數(shù)據(jù)

3、葉子節(jié)點(diǎn)兩兩指針相互連接(符合磁盤的預(yù)讀特性)，順序查詢性能更高

注意：在B+Tree上有兩個(gè)頭指針，一個(gè)指向根節(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)，而且所有葉子節(jié)點(diǎn)(即數(shù)據(jù)節(jié)點(diǎn))之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)。因此可以對(duì) B+Tree 進(jìn)行兩種查找運(yùn)算：一種是對(duì)于主鍵的范圍查找和分頁查找，另一種是從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找。

1、InnoDB是通過B+Tree結(jié)構(gòu)對(duì)主鍵創(chuàng)建索引，然后葉子節(jié)點(diǎn)中存儲(chǔ)記錄，如果沒有主鍵，那么會(huì)選擇唯一鍵，如果沒有唯一鍵，那么會(huì)生成一個(gè)6位的row_id來作為主鍵。

2、如果創(chuàng)建索引的鍵是其他字段，那么在葉子節(jié)點(diǎn)中存儲(chǔ)的是該記錄的主鍵，然后再通過主鍵索引找到對(duì)應(yīng)的記錄,叫做回表。