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

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

作用：

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

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

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

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

索引的使用：

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

 操作：

注意:

        索引的創(chuàng)建也是一個(gè)危險(xiǎn)操作?。。?/span>
針對(duì)空表或者數(shù)據(jù)量比較小的表中創(chuàng)建索引沒有任何問題，但如果表中數(shù)據(jù)很大，此時(shí)創(chuàng)建索引將會(huì)引起大量的CPU/硬盤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)，加快了查詢速度！

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

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

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

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

        3.哈希表 

哈希表

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

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

        4.樹

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

AVL樹

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

紅黑樹

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

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

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

B樹：

以上是B樹的大概形狀

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

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

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

B+樹：

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

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

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

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

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

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

B+樹搜索：

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

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

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

1）遍歷有主鍵索引的列 

SELECT * FROM employees WHERE id = 5;

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

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

SELECT * FROM EMPLOYEES WHERE NAME = 'zhangsan' ;

 MySQL 只能通過全表掃描來查找數(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+樹找到對(duì)應(yīng)葉子節(jié)點(diǎn)，但此時(shí)非主鍵索引的B+樹的葉子節(jié)點(diǎn)存儲(chǔ)的都是主鍵Id，因此找到Id之后，再在id主鍵索引的B+樹中遍歷 找到對(duì)應(yīng)的葉子節(jié)點(diǎn)，此時(shí)葉子節(jié)點(diǎn)才正在存儲(chǔ)我們想要找到的數(shù)據(jù)；

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

總結(jié)： 

• 沒有索引的情況下，MySQL 只能通過全表掃描來查找數(shù)據(jù)，效率較低，尤其在表的數(shù)據(jù)量較大時(shí)。
• 使用 B+ 樹索引的情況下，MySQL 可以通過 B+ 樹的查找機(jī)制（O(log N) 的復(fù)雜度）高效地定位記錄，從而大大提升查詢性能。B+ 樹支持點(diǎ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)論