索引的認(rèn)識(shí)：

索引是數(shù)據(jù)庫(kù)中的一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于加速查詢(xún)操作。

作用：

• 數(shù)據(jù)庫(kù)中的表、數(shù)據(jù)、索引之間的關(guān)系，類(lèi)似于書(shū)架上的圖書(shū)、書(shū)籍內(nèi)容和書(shū)籍目錄的關(guān)系。
• 索引所起的作用類(lèi)似書(shū)籍目錄，可用于快速定位、檢索數(shù)據(jù)。
• 索引對(duì)于提高數(shù)據(jù)庫(kù)的性能有很大的幫助

比如一本字典，如果一一的查找，這個(gè)效率將會(huì)很低下。

但如果給它加上標(biāo)簽的話(huà)，就一下可以找到你想搜索的東西，所有它大大提高了我們的查詢(xún)速度。

索引可以提高查詢(xún)速度，但可能會(huì)拖慢增刪改的速度，后續(xù)對(duì)數(shù)據(jù)進(jìn)行增刪改的操作，都是要同步索引的。但在實(shí)際開(kāi)發(fā)中，查詢(xún)的頻率要遠(yuǎn)遠(yuǎn)高于增刪改的操作，所以這是利大于弊

索引的使用：

//查看索引
show index from 表名;
//創(chuàng)建索引
//對(duì)于非主鍵、非唯一約束、非外鍵的字段，可以創(chuàng)建普通索引
create index 索引名 on 表名(字段名);
//刪除索引
drop index 索引名 on 表名;

 操作：

注意:

        索引的創(chuàng)建也是一個(gè)危險(xiǎn)操作?。?！
針對(duì)空表或者數(shù)據(jù)量比較小的表中創(chuàng)建索引沒(méi)有任何問(wèn)題，但如果表中數(shù)據(jù)很大，此時(shí)創(chuàng)建索引將會(huì)引起大量的CPU/硬盤(pán)IO的消耗，可能會(huì)把MySQL直接搞掛；

        解法方法：

1.預(yù)測(cè)哪個(gè)索引可能會(huì)頻繁使用，根據(jù)建議，提前給它創(chuàng)建好
2.引入新的數(shù)據(jù)庫(kù)服務(wù)器，提取創(chuàng)建好索引，將舊的數(shù)據(jù)庫(kù)服務(wù)器數(shù)據(jù)慢慢導(dǎo)入到新服務(wù)器中（常規(guī)做法）；

索引底層的數(shù)據(jù)結(jié)構(gòu)：

索引一定是引入了一些額外的數(shù)據(jù)結(jié)構(gòu)，加快了查詢(xún)速度！

引入索引的目的，就是通過(guò)其他的數(shù)據(jù)結(jié)構(gòu)，來(lái)加快查詢(xún)的速度，以便減小表的遍歷！

那么哪些數(shù)據(jù)結(jié)構(gòu)可以加快查詢(xún)速度？

        1.順序表： 隨機(jī)訪(fǎng)問(wèn)，并且插入刪除效率低下 不適合加快查詢(xún)速度

        2.鏈表：從頭依次遍歷，更不能加快查詢(xún)速度

        3.哈希表 

哈希表

    眾所周知，哈希表查詢(xún)速度是最快的，構(gòu)造出合適的哈希函數(shù)，可以達(dá)到O(1)查詢(xún)速度,即使在極端情況下，將所有值通過(guò)哈希函數(shù)映射到一個(gè)同哈希桶上，達(dá)到O(N)，這種情況一般只存在于理論上，現(xiàn)實(shí)中幾乎不可能出現(xiàn)。最壞情況下，設(shè)置哈希桶上的每個(gè)鏈表長(zhǎng)度為M，O(M)也是近視O(1)。      

    雖然哈希表的查詢(xún)速度特別快，但是它只能查找特定的某個(gè)值（key），并不是一連串的范圍，但數(shù)據(jù)庫(kù)中一般要我們查找的情況下是一系列的范圍數(shù)據(jù)，所以并不適合數(shù)據(jù)庫(kù)查詢(xún)；

        4.樹(shù)

二叉搜索樹(shù)的數(shù)據(jù) 中序遍歷是連續(xù)范圍的數(shù)據(jù) 是有序的，可以進(jìn)行范圍查詢(xún)，如果是一個(gè)比較平衡的二叉樹(shù)搜索樹(shù) 遍歷速度O(logN)  最壞情況下變成一個(gè)鏈表，就會(huì)變成O(N)速度

AVL樹(shù)

是一顆嚴(yán)格的二叉搜索樹(shù)，左右子樹(shù)高度不能超過(guò)1 所以遍歷速度O(logN)  但是當(dāng)你非常嚴(yán)格的情況下，每次進(jìn)行增刪改的操作，從而觸發(fā)旋轉(zhuǎn)操作，每次旋轉(zhuǎn)，都會(huì)有開(kāi)銷(xiāo)。

紅黑樹(shù)

而紅黑樹(shù)并沒(méi)有AVL樹(shù)那么嚴(yán)格，觸發(fā)旋轉(zhuǎn)的概率很小，雖然沒(méi)有AVL樹(shù)平衡，但是查詢(xún)速度也沒(méi)差多少

紅黑樹(shù)里面的數(shù)據(jù) 中序遍歷是連續(xù)范圍的數(shù)據(jù) 是有序的，可以進(jìn)行范圍查詢(xún)，但由于它是二叉類(lèi)型的，如果數(shù)據(jù)量特別大，這會(huì)讓樹(shù)的高度變得非常高，樹(shù)的高度每加一層，比較次數(shù)就會(huì)增加一次，由于數(shù)據(jù)都是保存在硬盤(pán)中，就會(huì)多要一次硬盤(pán)IO操作了，它查詢(xún)的效率就會(huì)變得慢，所以并不適合大規(guī)模的數(shù)據(jù)

 因此就引入了B樹(shù)，它是一個(gè)N叉搜索樹(shù)，同樣數(shù)量的數(shù)據(jù)，需要的節(jié)點(diǎn)變少了，樹(shù)的高度大大降低了，從而減小了遍歷的次數(shù)。

B樹(shù)：

以上是B樹(shù)的大概形狀

1.每個(gè)節(jié)點(diǎn)上的key是有序的，比較的時(shí)候可以直接用二分查找

2.B樹(shù)會(huì)控制每個(gè)節(jié)點(diǎn)上的key的數(shù)量，如果key太多，就會(huì)分裂更多的葉子節(jié)點(diǎn)出來(lái)

3.多個(gè)數(shù)據(jù)，都是放在一塊連續(xù)的存儲(chǔ)空間上，比較的時(shí)候，使用一次IO就可以遍歷完整個(gè)節(jié)點(diǎn) 因此B樹(shù)更適合對(duì)應(yīng)這種數(shù)據(jù)量的范圍查找，但數(shù)據(jù)庫(kù)索引的最終形態(tài)是B+樹(shù)，B樹(shù)的升級(jí)版

B+樹(shù)：

B+樹(shù)也是N叉樹(shù) 對(duì)比B樹(shù) B+樹(shù)做了進(jìn)一步優(yōu)化

1.B+樹(shù)每個(gè)父節(jié)點(diǎn)的元素都會(huì)在子節(jié)點(diǎn)的最大值出現(xiàn)

2. B樹(shù)的每個(gè)節(jié)點(diǎn)都包含鍵值（Key）和相應(yīng)的值（Value）（包括葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)）。而B+樹(shù)非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值（Key）也就是ID，葉子節(jié)點(diǎn)存儲(chǔ)所有的數(shù)據(jù)，并且每個(gè)葉子節(jié)點(diǎn)是以鏈表結(jié)構(gòu)存儲(chǔ)起來(lái)的，B+樹(shù)可以通過(guò)簡(jiǎn)單的順序訪(fǎng)問(wèn)葉子節(jié)點(diǎn)來(lái)高效地執(zhí)行范圍查詢(xún)。

3.進(jìn)行每次查詢(xún)操作，都會(huì)落到最終的葉子節(jié)點(diǎn)上，每次經(jīng)歷的硬盤(pán)IO次數(shù)都是穩(wěn)定的（穩(wěn)定做一件事在計(jì)算機(jī)中很重要）

4. B+樹(shù)的非葉子節(jié)點(diǎn)都存儲(chǔ)的數(shù)據(jù)比較小，所有可以存儲(chǔ)在內(nèi)存中，進(jìn)一步減小硬盤(pán)IO的次數(shù)

Mysql中支持多種存儲(chǔ)引擎，其中InnoDB最常用（也是面試做?？疾榈膬?nèi)容），不同的存儲(chǔ)引擎使用的索引也是不同的 

B+樹(shù)搜索：

下面來(lái)介紹B+樹(shù)在有無(wú)索引的情況下如何檢索：

CREATE TABLE employees (
    id INT PRIMARY KEY,
    name VARCHAR(50),
    age INT
);

在這張表中，id為主鍵，所有默認(rèn)會(huì)創(chuàng)建索引，name和age列則沒(méi)創(chuàng)建索引

1）遍歷有主鍵索引的列 

SELECT * FROM employees WHERE id = 5;

MySQL 會(huì)利用 B+ 樹(shù)索引，直接從根節(jié)點(diǎn)開(kāi)始查找，快速定位到 id = 5 的葉子節(jié)點(diǎn)，查詢(xún)的時(shí)間復(fù)雜度為 O(log N)。 

2）遍歷無(wú)索引的列 

SELECT * FROM EMPLOYEES WHERE NAME = 'zhangsan' ;

 MySQL 只能通過(guò)全表掃描來(lái)查找數(shù)據(jù)，效率較低，尤其在表的數(shù)據(jù)量較大時(shí)。

3） 遍歷有索引的列卻不是主鍵索引

create index index_id on employees(age) ;

 此時(shí)為age列創(chuàng)建索引

select * from employees where age = 20 ;

此時(shí)根據(jù)關(guān)于age的B+樹(shù)找到對(duì)應(yīng)葉子節(jié)點(diǎn)，但此時(shí)非主鍵索引的B+樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)的都是主鍵Id，因此找到Id之后，再在id主鍵索引的B+樹(shù)中遍歷 找到對(duì)應(yīng)的葉子節(jié)點(diǎn)，此時(shí)葉子節(jié)點(diǎn)才正在存儲(chǔ)我們想要找到的數(shù)據(jù)；

因此需要遍歷倆次B+樹(shù)，第一次找到主鍵Id，再在主鍵Id的B+樹(shù)找到對(duì)應(yīng)的值；

總結(jié)： 

• 沒(méi)有索引的情況下，MySQL 只能通過(guò)全表掃描來(lái)查找數(shù)據(jù)，效率較低，尤其在表的數(shù)據(jù)量較大時(shí)。
• 使用 B+ 樹(shù)索引的情況下，MySQL 可以通過(guò) B+ 樹(shù)的查找機(jī)制（O(log N) 的復(fù)雜度）高效地定位記錄，從而大大提升查詢(xún)性能。B+ 樹(shù)支持點(diǎn)查詢(xún)和范圍查詢(xún)，尤其對(duì)于大數(shù)據(jù)量的表，具有非常重要的優(yōu)化作用。

到此這篇關(guān)于MySQL索引背后的內(nèi)部結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)mysql索引結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論