目錄

索引(INDEX)基本概念

索引結(jié)構(gòu)分類

B+Tree樹索引結(jié)構(gòu)

Hash索引結(jié)構(gòu)

Full-Text索引

R-Tree索引

索引(INDEX)基本概念

什么是索引

索引是幫助MySQL高效獲取數(shù)據(jù)的有序數(shù)據(jù)結(jié)構(gòu)

為數(shù)據(jù)庫表中的某些列創(chuàng)建索引，就是對數(shù)據(jù)庫表中某些列的值通過不同的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序

為列建立索引之后，數(shù)據(jù)庫除了維護(hù)數(shù)據(jù)之外，還會(huì)維護(hù)滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式指向數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)快速查詢，這種數(shù)據(jù)結(jié)構(gòu)就是索引

索引的作用

通過索引可以將無序的數(shù)據(jù)變?yōu)橛行虻臄?shù)據(jù)，能夠?qū)崿F(xiàn)快速訪問數(shù)據(jù)庫表中的特定信息

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

提高數(shù)據(jù)檢索的效率，降低數(shù)據(jù)庫的IO成本

通過索引對數(shù)據(jù)進(jìn)行排序，降低數(shù)據(jù)排序的成本，降低CPU的消耗

缺點(diǎn)

索引會(huì)占用空間

索引提高了表的查詢效率，但是卻降低了更新表的速度（Insert、Update、Delete）

索引只是一個(gè)提高效率的因素，如果MySQL有大數(shù)據(jù)量的表，就需要花時(shí)間研究最優(yōu)秀的索引（即需要研究為哪些字段建立索引能夠使得效率提升到最大化，因?yàn)橐粭l查詢語句只會(huì)引用到一種索引，并且一般建議一個(gè)表建立的索引數(shù)量不要超過5個(gè)）

索引結(jié)構(gòu)分類

索引結(jié)構(gòu)主要分為四大類

B+Tree索引-（B+樹）

最常見的索引類型，大部分的存儲(chǔ)引擎都支持此索引

Hash索引-（Hash表）

底層的數(shù)據(jù)結(jié)構(gòu)是用哈希表實(shí)現(xiàn)的，只有精確匹配索引列的查詢才有效，不支持范圍查詢

Full-Text索引-（倒排索引）

又名全文索引，是一種通過建立倒排索引，快速匹配文檔的方式

R-Tree索引（R-Tree樹）

又名空間索引，是MyISAM引擎的一個(gè)特殊索引類型，主要用于地理位置數(shù)據(jù)，使用較少

存儲(chǔ)引擎對不同索引的支持情況（默認(rèn)B+Tree索引）

?在MySQL數(shù)據(jù)庫中，支持Hash索引的是Memory引擎；而InnoDB中具有自適應(yīng)Hash的功能，根據(jù)B+tree索引在指定條件下自動(dòng)構(gòu)建的

B+Tree樹索引結(jié)構(gòu)

B+Tree樹是由二叉樹 → 紅黑樹（自平衡二叉樹） → B-Tree樹煙花而來的，我們在介紹B+Tree樹之前先介紹這三種數(shù)據(jù)結(jié)構(gòu)

二叉樹

二叉樹的每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)（兩顆子樹）；并且兩個(gè)子節(jié)點(diǎn)是有序的

以單個(gè)節(jié)點(diǎn)為例：左邊子節(jié)點(diǎn)是比自身小的，右邊子節(jié)點(diǎn)是比自身大的

缺點(diǎn)

1. 大數(shù)據(jù)量的情況下，層級(jí)較深，檢索速度慢
2. 容易形成傾斜樹（左傾斜或右傾斜）

?二叉樹的工作原理

?二叉樹的數(shù)據(jù)插入（依次插入30、40、20、19、21、39、35）

?二叉樹的數(shù)據(jù)遍歷

?二叉樹的數(shù)據(jù)查找（查找39 、21、25）

?二叉樹的數(shù)據(jù)刪除（依次刪除19、39、30）

紅黑樹（自平衡二叉樹）

紅黑樹時(shí)二叉樹的變種，可以解決二叉樹插入數(shù)值時(shí)產(chǎn)生斜樹的問題

任何一個(gè)節(jié)點(diǎn)都有顏色(紅色或黑色)，通過顏色來確保樹在插入和刪除時(shí)的平衡

根節(jié)點(diǎn)一定是黑色的；Null節(jié)點(diǎn)被認(rèn)為是黑色的；每個(gè)紅色節(jié)點(diǎn)的兩個(gè)葉子節(jié)點(diǎn)都是黑色

每個(gè)葉子節(jié)點(diǎn)到根的路徑上不能出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)

任何一個(gè)節(jié)點(diǎn)到達(dá)葉子節(jié)點(diǎn)所經(jīng)過的黑節(jié)點(diǎn)個(gè)數(shù)必須相等

當(dāng)在紅黑樹中進(jìn)行插入和刪除操作時(shí)，會(huì)通過左旋、右旋、重新著色來修復(fù)樹結(jié)構(gòu)，保持樹的平衡

缺點(diǎn)

1. 在進(jìn)行大量插入和刪除操作的情況下，可能會(huì)造成頻繁的樹重構(gòu)，影響性能
2. 紅黑樹的實(shí)現(xiàn)比較復(fù)雜，需要維護(hù)節(jié)點(diǎn)的顏色和平衡
3. 紅黑樹本質(zhì)也是二叉樹，在大數(shù)據(jù)量的情況下，層級(jí)較深，檢索速度會(huì)下降

紅黑樹的工作原理

紅黑樹的數(shù)據(jù)插入（依次插入30、40、20、19、21、39、35） ?使用到了右旋

紅黑樹的數(shù)據(jù)遍歷

紅黑樹的數(shù)據(jù)查找（查找39 、21、25）

紅黑樹的數(shù)據(jù)刪除（依次刪除19、39、30）

B-Tree樹（多路平衡查找樹）

二叉樹一個(gè)Node節(jié)點(diǎn)只能夠存儲(chǔ)一個(gè)Key和一個(gè)Value，并且只有兩個(gè)子節(jié)點(diǎn)；而多路樹相比較而言一個(gè)Node節(jié)點(diǎn)能夠存儲(chǔ)更多的Key和Value，能夠攜帶更多的子節(jié)點(diǎn)，建樹高度會(huì)比二叉樹要低

B-Tree樹的一個(gè)節(jié)點(diǎn)能夠存儲(chǔ)多少Key和Value，可以有多少個(gè)子節(jié)點(diǎn)通過最大度數(shù)（MAX-Degree 也稱為階數(shù)）決定

一個(gè)m階的B-Tree樹

?????? 樹中的每個(gè)節(jié)點(diǎn)最多有m個(gè)子節(jié)點(diǎn)，m-1個(gè)Key和Value（兩個(gè)子樹的指針夾著一個(gè)Key和Value）

?????? 樹的根節(jié)點(diǎn)至少有一個(gè)Key和Value，至少兩個(gè)子節(jié)點(diǎn)

缺點(diǎn)

B樹的葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都會(huì)保存數(shù)據(jù)，使得非葉子節(jié)點(diǎn)保存的指針量變小

如果存儲(chǔ)大量的數(shù)據(jù)，需要增加樹的高度，導(dǎo)致IO操作變多，查詢性能變低

B-Tree樹的工作原理

B-Tree樹的數(shù)據(jù)插入Max-Degree為3（依次插入30、40、20、19、21、39、35）

B-Tree樹的數(shù)據(jù)遍歷

B-Tree樹的數(shù)據(jù)查找（查找39 、21、25）

B-Tree樹的數(shù)據(jù)刪除（依次刪除19、39、30）

B+Tree樹

B+Tree樹是B-Tree樹的變種，也是一種多路搜索樹，定義基本與B-Tree相同

B+Tree只有葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，并且所有的元素都會(huì)出現(xiàn)在葉子節(jié)點(diǎn)中，所有葉子節(jié)點(diǎn)形成了一個(gè)單向鏈表；葉子節(jié)點(diǎn)將數(shù)據(jù)按照大小排列，并且相鄰葉子節(jié)點(diǎn)之間按照大小排列

非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)Key，只是起到索引的作用，在相同的數(shù)據(jù)量下，B+Tree樹更加矮壯

B+Tree樹的工作原理

B+Tree樹的數(shù)據(jù)插入Max-Degree為3（依次插入30、40、20、19、21、39、35）

B+Tree樹的數(shù)據(jù)遍歷

B+Tree樹的數(shù)據(jù)查找（查找39 、21、25）

B+Tree樹的數(shù)據(jù)刪除（依次刪除19、39、30）

MySQL的B+Tree索引結(jié)構(gòu)

MySQL的索引數(shù)據(jù)結(jié)構(gòu)對經(jīng)典的B+Tree進(jìn)行了優(yōu)化，在原B+Tree的基礎(chǔ)上，增加了一個(gè)指向相鄰葉子節(jié)點(diǎn)的鏈表指針，所有葉子節(jié)點(diǎn)形成了一個(gè)雙向鏈表，提高了遍歷速度

MySQL在查詢是根據(jù)查詢條件查詢對應(yīng)的鍵值（Key），然后將鍵值對應(yīng)數(shù)據(jù)（Value）提取出來

Hash索引結(jié)構(gòu)

哈希索引就是采用一定的hash算法，將鍵值換算成新的Hash值，將哈希值映射到一個(gè)桶中，桶中存儲(chǔ)了所有哈希值相同的數(shù)據(jù)行的指針，然后存儲(chǔ)在Hash表中；

當(dāng)查詢時(shí)，MySQL會(huì)先通過哈希函數(shù)計(jì)算出查詢條件的哈希值，在Hash表中查找對應(yīng)的桶，然后在對應(yīng)的桶中查找相應(yīng)的數(shù)據(jù)行

哈希沖突

如果兩個(gè)或多個(gè)鍵值，映射到同一個(gè)相同的槽位（桶），則他們就產(chǎn)生了hash沖突，通過鏈表解決

?特點(diǎn)

1. Hash索引只能夠用于對等比較（=，in等），不支持范圍查詢（between，>，<等）
2. 無法利用Hash索引完成排序操作；因?yàn)镠ash索引中存放的是經(jīng)過Hash計(jì)算后的Hash值，此值的大小并不一定和Hash運(yùn)算之前的鍵值完全一樣
3. Hash索引無法避免表掃描，即每次都要全表掃描；因?yàn)镠ash索引是將鍵值通過Hash運(yùn)算之后，將其結(jié)果和對應(yīng)的行指針信息存放在一個(gè)Hash表中，由于不同的索引鍵可能存在相同的Hash值，也就是哈希沖突，所以滿足某個(gè)Hash鍵值的數(shù)據(jù)的記錄跳數(shù)，無法直接從Hash索引中直接完成查詢，還是要通過訪問表中的實(shí)際數(shù)據(jù)進(jìn)行比較，并得到相應(yīng)的結(jié)果
4. 對于聯(lián)合索引，Hash不能使用部分索引鍵查詢（要么全部使用，要么全部不使用）
5. Hash只需要做一次運(yùn)算，就可以找到該數(shù)據(jù)所在的桶；不像樹結(jié)構(gòu)那樣從根、葉子節(jié)點(diǎn)的順序來查找；所以Hash索引的查詢效率理論上是要高于B+Tree的；不過對于存在大量Hash值相同的情況下，性能不一定比B+Tree高

Full-Text索引

通過建立倒排索引（Inverted Index）構(gòu)建Full-Text索引，提高數(shù)據(jù)的檢索效率

倒排索引是一種將文檔中的單詞/漢字映射到其出現(xiàn)位置的數(shù)據(jù)結(jié)構(gòu)，主要用來解決判斷字段的值中 是否包含 某字符/漢字的問題

我們對于簡單業(yè)務(wù)或者數(shù)據(jù)量小的業(yè)務(wù)，可以通過Like()關(guān)鍵字來判斷；但是對于大數(shù)據(jù)量業(yè)務(wù)，使用Like效率會(huì)大大降低

不同存儲(chǔ)索引對Full-Text索引的支持

在MySQL5.6版本之前，只有MYISAM存儲(chǔ)引擎支持全文索引

在MySQL5.6版本之后，InnoDB能夠支持全文索引；不過只支持對英文的全文索引，不支持中文的全文索引；后續(xù)通過內(nèi)置分詞器（ngram）來支持中文索引

配置ngram的最小長度

在MySQL的配置文件中添加以下字段

ft_min_word_len = 2???? #此最小長度就是分詞的最小長度，默認(rèn)為2

即：對于一段語句，可以分為多個(gè)漢字組，每個(gè)漢字組最少都有2個(gè)漢字

??? 我想學(xué)習(xí)數(shù)據(jù)庫 ?可以分詞為： 我想 學(xué)習(xí) ?數(shù)據(jù)庫 三個(gè)組

一般不會(huì)將ngram設(shè)置的很小，如果很小的話會(huì)占用大量的空間，因此我們一般都不修改此最小長度，就默認(rèn)為2

全文索引的流程

用戶輸入要查找的內(nèi)容 → SQL執(zhí)行引擎 → ngram對查找的內(nèi)容進(jìn)行分詞 → 把分詞后的詞依次的去倒排索引中去查找 → 將相應(yīng)的記錄返回

分詞器ngram在建立索引時(shí)會(huì)對字段中的值進(jìn)行分詞；在進(jìn)行查詢時(shí)也會(huì)對要查找的內(nèi)容分詞

R-Tree索引

構(gòu)建空間索引有多種數(shù)據(jù)結(jié)構(gòu)，例如四叉樹、R-Tree樹

在MySQL中是通過R-Tree樹來構(gòu)建空間索引的，是一種加快空間數(shù)據(jù)查詢速度的技術(shù)

R-tree將空間數(shù)據(jù)分割成一系列矩形區(qū)域，每個(gè)節(jié)點(diǎn)可以表示一個(gè)矩形區(qū)域，同時(shí)可以包含其他節(jié)點(diǎn)或數(shù)據(jù)項(xiàng)。這種層級(jí)結(jié)構(gòu)允許MySQL在空間查詢中更快地定位所需的數(shù)據(jù)，減少搜索范圍，從而提高查詢性能

例如：

一個(gè)表中的某字段存儲(chǔ)著一個(gè)地方餐館的經(jīng)緯度位置信息，現(xiàn)在我們需要根據(jù)我們的位置，找附近1公里的餐館

我們可以通過計(jì)算我們的位置，找到附近1公里范圍內(nèi)的經(jīng)緯度范圍，然后查詢表中的滿足此經(jīng)緯度的值；為了加快檢索效率，我們就可以對存儲(chǔ)經(jīng)緯度位置信息的字段建立空間索引

R-Tree的構(gòu)建過程——R樹是把B樹的思想擴(kuò)展到了多維空間

1、數(shù)據(jù)劃分

所有的數(shù)據(jù)項(xiàng)也成為對象（點(diǎn)、線或面）都被視為一個(gè)單獨(dú)的矩形

2、構(gòu)建葉子節(jié)點(diǎn)（葉子節(jié)點(diǎn)是R樹的底層節(jié)點(diǎn)）

將劃分好的矩形進(jìn)行分組，并構(gòu)建葉子節(jié)點(diǎn)；每個(gè)葉子節(jié)點(diǎn)包含多個(gè)對象及其對應(yīng)的矩形

3、合并葉子節(jié)點(diǎn)

當(dāng)葉子節(jié)點(diǎn)的數(shù)目超過了R-Tree規(guī)定的最大容量，此時(shí)R樹會(huì)嘗試合并相鄰的葉子節(jié)點(diǎn)來減少樹的高度和提高查詢效率

4、構(gòu)建非葉子節(jié)點(diǎn)

將合并后葉子構(gòu)建為新的非葉子節(jié)點(diǎn)；非葉子節(jié)點(diǎn)也是一個(gè)矩形，包含了其所有子節(jié)點(diǎn)的矩形范圍

5、遞歸構(gòu)建

重復(fù)上述的操作，知道構(gòu)建出整個(gè)R樹的根節(jié)點(diǎn)（R樹的最頂層節(jié)點(diǎn)，將包含所有的數(shù)據(jù)范圍）

具體R樹的構(gòu)建方式可以參考以下文章

從B樹、B+樹、B*樹談到R 樹_v_JULY_v的博客-CSDN博客https://blog.csdn.net/v_JULY_v/article/details/6530142文章來源地址http://www.zghlxwxcb.cn/news/detail-633273.html

到了這里，關(guān)于MySQL索引1——索引基本概念與索引結(jié)構(gòu)（B樹、R樹、Hash等）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！