mysql索引內(nèi)部實現(xiàn)與算法分析

本篇內(nèi)容主要講解“mysql索引內(nèi)部實現(xiàn)與算法分析”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“mysql索引內(nèi)部實現(xiàn)與算法分析”吧!

存儲引擎從索引的根節(jié)點開始進行搜索，通過節(jié)點槽中的指針向下層查找，比較節(jié)點頁的值和要查找的值找到合適的指針進入下層子節(jié)點。存儲引擎最終要么找到對應的值，要么該記錄不存在。

葉子節(jié)點的指針指向的是被索引的數(shù)據(jù)，而不是其他的節(jié)點頁
索引可以按值查找之外，還可以用于查詢中的order by操作(原因：索引樹中的節(jié)點是有序的)
B+tree索引的限制：

    1.如果不是按照索引的最左列開始查找，則無法使用索引

    2.不能跳過索引中的列

    3.如果查詢中有某個列的范圍查找，則其右邊所有列都無法使用索引優(yōu)化查找

B+樹的插入操作

B+樹的插入必須保證插入后葉節(jié)點中的記錄依然排序，

插入B+樹的三種情況

第一種情況，往圖中插入28，leaf page和index page都沒有滿，直接插入

第二種情況，往圖中插入70，leaf page滿了，index page沒有滿

說明：采用旋轉(zhuǎn)操作使得其減少一次頁的拆分操作

第三種情況，在圖中插入95，leaf page和index page都滿了

說明：B+樹為了保持平衡，對新插入的鍵值可能需要大量的拆分頁操作，但是B+樹主要用于磁盤，我們應該盡可能減少頁的拆分，可以通過旋轉(zhuǎn)功能（leaf page已經(jīng)滿了，但是左右兄弟節(jié)點沒有滿）

B+樹的刪除操作

B+樹使用填充因子來控制樹的刪除變化，50%是填充因子可設(shè)的最小資。同樣必須保證刪除后葉節(jié)點中的記錄依然排序。

刪除B+樹（根據(jù)填充因子的變化來衡量）的三種情況

在圖中刪除70

在圖中刪除25，此時25的兄弟節(jié)點的28更新到page index中

在圖中刪除60，此時填充因子小于50%，需要做合并操作

B+樹索引

B+樹索引本質(zhì)是在B+樹在數(shù)據(jù)庫中的實現(xiàn) 特點：扇出性

數(shù)據(jù)庫中B+樹索引分為：聚集索引（clustered index）、輔助聚集索引（secondary index）

索引組織表：表中數(shù)據(jù)按照主鍵順序存放

堆表：按照插入數(shù)據(jù)順序存放，堆表上的索引都是非聚集的，且堆表沒有主鍵

    聚集索引(每張表只有一個):按照每張表的主鍵構(gòu)造一棵B+樹，且葉節(jié)點存放著整張表的行記錄數(shù)據(jù)，所以聚集索引的葉節(jié)點也成了數(shù)據(jù)頁，

    輔助聚集索引的葉節(jié)點上存放的僅僅是鍵值以及指向數(shù)據(jù)頁的偏移量，不是一個完整行記錄
聚集索引不是一種單獨的索引類型，而是一種數(shù)據(jù)存儲方式。innodb的聚集索引實際上在同一個結(jié)構(gòu)中保存了B+tree索引和數(shù)據(jù)行。

當表有聚集索引時，數(shù)據(jù)行實際上是存儲在索引的葉子頁中

說明：聚集索引的存儲在物理上是不連續(xù)的，在邏輯上是連續(xù)的：1.頁通過雙向鏈表鏈接，頁按照主鍵的順序排序；2.每個頁中的記錄也是通過雙向鏈表進行維護，物理存儲上可以同樣不按照主鍵存儲

聚集索引的優(yōu)點：

    可以把相關(guān)數(shù)據(jù)保存在一起

    數(shù)據(jù)訪問更快(聚集索引將索引和數(shù)據(jù)保存在同一個b+tree中)

    使用覆蓋索引掃描的查詢可以直接使用頁節(jié)點中的主鍵值

聚集索引的缺點：

    聚集數(shù)據(jù)提高了IO性能，如果數(shù)據(jù)全部放在內(nèi)存中，則訪問的順序就沒那么重要了

    插入速度嚴重依賴插入順序。按主鍵的順序插入是速度最快的。但如果不是按照主鍵順序加載數(shù)據(jù)，則需在加載完成后最好使用optimize table重新組織一下表

    更新聚集索引列的代價很高。因為會強制innod將每個被更新的行移動到新的位置

    基于聚集索引的表在插入新行，或主鍵被更新導致需要移動行的時候，可能面臨頁分裂的問題。頁分裂會導致表占用更多的磁盤空間。

    聚集索引可能導致全表掃描變慢，尤其是行比較稀疏，或由于頁分裂導致數(shù)據(jù)存儲不連續(xù)的時

    非聚集索引比想象的更大，因為二級索引的葉子節(jié)點包含了引用行的主鍵列

    非聚集索引訪問需要兩次索引查找(非聚集索引中葉子節(jié)點保存的行指針指向的是行的主鍵值)，對于innodb自適應哈希索引可以減少這樣的重復工作

輔助索引：葉節(jié)點包含鍵值，且每個葉級別的索引行還包含一個書簽（相應行數(shù)據(jù)的聚集索引）

輔助索引和聚集索引的關(guān)系圖

說明：輔助索引的存在不影響數(shù)據(jù)在聚集索引中的組織，所以每張表可以有多個輔助索引

原理：通過輔助索引來尋找數(shù)據(jù)時過程：innodb會遍歷輔助索引并通過葉級別的指針獲得指向主鍵索引的主鍵，然后再通過主鍵索引來找到一個完整的行記錄。

B+樹索引的管理

索引的創(chuàng)建和刪除的方法：alter table；create /drop   index

創(chuàng)建主鍵索引過程：先創(chuàng)建一張新的臨時表，然后將數(shù)據(jù)導入臨時表，刪除原表，再把臨時表重名為原來的表名

創(chuàng)建輔助索引過程：在創(chuàng)建過程中不需要重建表，只會對表加上一個S鎖，速度極快。

通過show index from table_name可以查看表中索引的信息

說明：

    table：索引所在的表名

    Non_unique:非唯一索引，primary key是0

    Key_name:索引的名稱

    Seq_in_index:索引中該列的位置

    Column_name：索引的列

    Collation:列以什么方式存儲在索引中，B+樹索引總是A，即排序；如果使用了heap存儲引擎，且建立了hash索引，就會顯示NULL，因為hash通過hash桶來存放索引數(shù)據(jù)，而不是對數(shù)據(jù)進行排序

    Cardinality:表示索引中唯一值的數(shù)目的估計值，Cardinality/表的行數(shù)  盡可能接近1，太小則需要重建該索引

    Sub_part:是否是列的部分被索引，如只索引某一列的前多少字符，如果索引整個列，則該字段為NULL

    packed：關(guān)鍵字如何被壓縮。沒有被壓縮則為NULL

    NULL：是否索引的列含有null值，

    Index_type:索引的類型，innodb只支持B+索引

    comment:注釋

B+樹索引的使用

當訪問高選擇性字段并從表中取出很少一部分行時，就需要對這個字段添加B+樹索引

注：當取出數(shù)據(jù)量超過表中數(shù)據(jù)的20%，優(yōu)化器就不會使用索引，而是進行全表的掃表。且預估的返回行數(shù)的值是不準確的

順序讀、隨機讀、預讀取

    順序讀（sequntial read）：順序地讀取磁盤上的塊（block）

    隨機讀（random read）：訪問的塊不是連續(xù)的，需要磁盤的磁頭不斷移動

    預讀?。╮ead ahead）：通過一次IO請求將多個頁預讀取到緩沖池中

    隨機預讀?。╮andom read ahead）：當一個區(qū)（64個連續(xù)頁）中13個頁也在緩沖區(qū)中，并在LRU列表的前端（即頁是被頻繁訪問），則innodb會將這個區(qū)剩余的所有頁預讀到緩沖區(qū)

    線性預讀?。╨inear read ahead）：基于緩沖池中頁的模式，而不是數(shù)量。如果一個區(qū)中的24個頁都被順序訪問了，則innodb會讀取下一個區(qū)的所有頁

innodb_read_ahead_threshold參數(shù)：表示一個區(qū)中的多少頁被順序訪問時，innodb才啟用預讀取。默認值為56，即當一個區(qū)中的56個頁被順序訪問時，則預讀取下個區(qū)的所有頁

聯(lián)合索引：還是一棵B+樹，不同的是聯(lián)合索引的鍵值的數(shù)量不是1，而是大于等于2

哈希算法

自適應哈希索引使用的是散列表（hash table）的數(shù)據(jù)結(jié)構(gòu)

哈希表（散列表）：由直接尋址表改進而來

哈希索引基于哈希表實現(xiàn)，只有精確匹配索引所有列的查詢才有效

原理：對每一行數(shù)據(jù)，存儲引擎會對所有的索引列計算一個哈希碼(很小且不同鍵值的行計算出的哈希碼也不一樣)，哈希索引將所有哈希碼存儲在索引中，同時也保存著每個數(shù)據(jù)行的指針。如果多個列的哈希值相同，索引會以鏈表的方式存放多個記錄指針到同一個哈希條目中

在mysql中，只有memory引擎顯示支持哈希索引(注：為非唯一哈希索引)，NDB支持唯一哈希索引，innodb支持自適應哈希索引

哈希索引的限制：

    1.哈希索引只包含哈希值和行指針，而不存儲字段值，索引不能使用索引的值來避免讀取行

    2.哈希索引數(shù)據(jù)并不是按照索引值順序存儲的，所以無法用于排序

    3.哈希索引不支持部分索引匹配查找(因為哈希索引始終是使用索引列的全部內(nèi)容來計算哈希值的)

    4.哈希索引只支持等值查詢，包括= ，in

    5.當出現(xiàn)哈希沖突(不同的索引列值卻有相同的哈希值)時，存儲引擎必須遍歷鏈表中所有的行指針，逐個比較直至找到符合條件的行

    6.如果哈希沖突很多，則索引維護操作的代價會很高（要避免哈希沖突，必須在where條件中帶入哈希值和對應列值）。

自適應哈希索引

通過Innodb_adaptive_hash_index參數(shù)可以開啟自適應哈希索引，數(shù)據(jù)庫啟動時會自動創(chuàng)建槽數(shù)為innodb_buffer_pool_size/256個哈希表

可以通過show engine innodb status查看當前自適應哈希索引的使用狀況

說明：包括哈希索引的大小，使用情況，每秒使用自適應哈希索引搜索的情況

注：哈希索引只能用來搜索等值的查詢，其他類型不能使用哈希索引

到此，相信大家對“mysql索引內(nèi)部實現(xiàn)與算法分析”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學習！