共計 3729 個字符，預計需要花費 10 分鐘才能閱讀完成。
本篇內容主要講解“mysql 索引內部實現與算法分析”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓丸趣 TV 小編來帶大家學習“mysql 索引內部實現與算法分析”吧!
存儲引擎從索引的根節點開始進行搜索，通過節點槽中的指針向下層查找，比較節點頁的值和要查找的值找到合適的指針進入下層子節點。存儲引擎最終要么找到對應的值，要么該記錄不存在。
葉子節點的指針指向的是被索引的數據，而不是其他的節點頁
索引可以按值查找之外，還可以用于查詢中的 order by 操作(原因：索引樹中的節點是有序的)
B+tree 索引的限制：
1. 如果不是按照索引的最左列開始查找，則無法使用索引
2. 不能跳過索引中的列
3. 如果查詢中有某個列的范圍查找，則其右邊所有列都無法使用索引優化查找
B+ 樹的插入操作
B+ 樹的插入必須保證插入后葉節點中的記錄依然排序，
插入 B + 樹的三種情況
第一種情況，往圖中插入 28，leaf page 和 index page 都沒有滿，直接插入
第二種情況，往圖中插入 70，leaf page 滿了，index page 沒有滿
說明：采用旋轉操作使得其減少一次頁的拆分操作
第三種情況，在圖中插入 95，leaf page 和 index page 都滿了
說明：B+ 樹為了保持平衡，對新插入的鍵值可能需要大量的拆分頁操作，但是 B + 樹主要用于磁盤，我們應該盡可能減少頁的拆分，可以通過旋轉功能（leaf page 已經滿了，但是左右兄弟節點沒有滿）
B+ 樹的刪除操作
B+ 樹使用填充因子來控制樹的刪除變化，50% 是填充因子可設的最小資。同樣必須保證刪除后葉節點中的記錄依然排序。
刪除 B + 樹（根據填充因子的變化來衡量）的三種情況
在圖中刪除 70
在圖中刪除 25，此時 25 的兄弟節點的 28 更新到 page index 中
在圖中刪除 60，此時填充因子小于 50%，需要做合并操作
B+ 樹索引
B+ 樹索引本質是在 B + 樹在數據庫中的實現 特點：扇出性
數據庫中 B + 樹索引分為：聚集索引（clustered index）、輔助聚集索引（secondary index）
索引組織表：表中數據按照主鍵順序存放
堆表：按照插入數據順序存放，堆表上的索引都是非聚集的，且堆表沒有主鍵
聚集索引(每張表只有一個): 按照每張表的主鍵構造一棵 B + 樹，且葉節點存放著整張表的行記錄數據，所以聚集索引的葉節點也成了數據頁，
輔助聚集索引的葉節點上存放的僅僅是鍵值以及指向數據頁的偏移量，不是一個完整行記錄
聚集索引不是一種單獨的索引類型，而是一種數據存儲方式。innodb 的聚集索引實際上在同一個結構中保存了 B +tree 索引和數據行。
當表有聚集索引時，數據行實際上是存儲在索引的葉子頁中
說明：聚集索引的存儲在物理上是不連續的，在邏輯上是連續的：1. 頁通過雙向鏈表鏈接，頁按照主鍵的順序排序；2. 每個頁中的記錄也是通過雙向鏈表進行維護，物理存儲上可以同樣不按照主鍵存儲
聚集索引的優點：
可以把相關數據保存在一起
數據訪問更快(聚集索引將索引和數據保存在同一個 b +tree 中)
使用覆蓋索引掃描的查詢可以直接使用頁節點中的主鍵值
聚集索引的缺點：
聚集數據提高了 IO 性能，如果數據全部放在內存中，則訪問的順序就沒那么重要了
插入速度嚴重依賴插入順序。按主鍵的順序插入是速度最快的。但如果不是按照主鍵順序加載數據，則需在加載完成后最好使用 optimize table 重新組織一下表
更新聚集索引列的代價很高。因為會強制 innod 將每個被更新的行移動到新的位置
基于聚集索引的表在插入新行，或主鍵被更新導致需要移動行的時候，可能面臨頁分裂的問題。頁分裂會導致表占用更多的磁盤空間。
聚集索引可能導致全表掃描變慢，尤其是行比較稀疏，或由于頁分裂導致數據存儲不連續的時
非聚集索引比想象的更大，因為二級索引的葉子節點包含了引用行的主鍵列
非聚集索引訪問需要兩次索引查找(非聚集索引中葉子節點保存的行指針指向的是行的主鍵值)，對于 innodb 自適應哈希索引可以減少這樣的重復工作
輔助索引：葉節點包含鍵值，且每個葉級別的索引行還包含一個書簽（相應行數據的聚集索引）
輔助索引和聚集索引的關系圖
說明：輔助索引的存在不影響數據在聚集索引中的組織，所以每張表可以有多個輔助索引
原理：通過輔助索引來尋找數據時過程：innodb 會遍歷輔助索引并通過葉級別的指針獲得指向主鍵索引的主鍵，然后再通過主鍵索引來找到一個完整的行記錄。
B+ 樹索引的管理
索引的創建和刪除的方法：alter table；create /drop index
創建主鍵索引過程：先創建一張新的臨時表，然后將數據導入臨時表，刪除原表，再把臨時表重名為原來的表名
創建輔助索引過程：在創建過程中不需要重建表，只會對表加上一個 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 桶來存放索引數據，而不是對數據進行排序
Cardinality: 表示索引中唯一值的數目的估計值，Cardinality/ 表的行數 盡可能接近 1，太小則需要重建該索引
Sub_part: 是否是列的部分被索引，如只索引某一列的前多少字符，如果索引整個列，則該字段為 NULL
packed：關鍵字如何被壓縮。沒有被壓縮則為 NULL
NULL：是否索引的列含有 null 值，
Index_type: 索引的類型，innodb 只支持 B + 索引
comment: 注釋
B+ 樹索引的使用
當訪問高選擇性字段并從表中取出很少一部分行時，就需要對這個字段添加 B + 樹索引
注：當取出數據量超過表中數據的 20%，優化器就不會使用索引，而是進行全表的掃表。且預估的返回行數的值是不準確的
順序讀、隨機讀、預讀取
順序讀（sequntial read）：順序地讀取磁盤上的塊（block）
隨機讀（random read）：訪問的塊不是連續的，需要磁盤的磁頭不斷移動
預讀取（read ahead）：通過一次 IO 請求將多個頁預讀取到緩沖池中
隨機預讀取（random read ahead）：當一個區（64 個連續頁）中 13 個頁也在緩沖區中，并在 LRU 列表的前端（即頁是被頻繁訪問），則 innodb 會將這個區剩余的所有頁預讀到緩沖區
線性預讀取（linear read ahead）：基于緩沖池中頁的模式，而不是數量。如果一個區中的 24 個頁都被順序訪問了，則 innodb 會讀取下一個區的所有頁
innodb_read_ahead_threshold 參數：表示一個區中的多少頁被順序訪問時，innodb 才啟用預讀取。默認值為 56，即當一個區中的 56 個頁被順序訪問時，則預讀取下個區的所有頁
聯合索引：還是一棵 B + 樹，不同的是聯合索引的鍵值的數量不是 1，而是大于等于 2
哈希算法
自適應哈希索引使用的是散列表（hash table）的數據結構
哈希表（散列表）：由直接尋址表改進而來
哈希索引基于哈希表實現，只有精確匹配索引所有列的查詢才有效
原理：對每一行數據，存儲引擎會對所有的索引列計算一個哈希碼(很小且不同鍵值的行計算出的哈希碼也不一樣)，哈希索引將所有哈希碼存儲在索引中，同時也保存著每個數據行的指針。如果多個列的哈希值相同，索引會以鏈表的方式存放多個記錄指針到同一個哈希條目中
在 mysql 中，只有 memory 引擎顯示支持哈希索引(注：為非唯一哈希索引)，NDB 支持唯一哈希索引，innodb 支持自適應哈希索引
哈希索引的限制：
1. 哈希索引只包含哈希值和行指針，而不存儲字段值，索引不能使用索引的值來避免讀取行
2. 哈希索引數據并不是按照索引值順序存儲的，所以無法用于排序
3. 哈希索引不支持部分索引匹配查找(因為哈希索引始終是使用索引列的全部內容來計算哈希值的)
4. 哈希索引只支持等值查詢，包括 =，in
5. 當出現哈希沖突 (不同的索引列值卻有相同的哈希值) 時，存儲引擎必須遍歷鏈表中所有的行指針，逐個比較直至找到符合條件的行
6. 如果哈希沖突很多，則索引維護操作的代價會很高（要避免哈希沖突，必須在 where 條件中帶入哈希值和對應列值）。
自適應哈希索引
通過 Innodb_adaptive_hash_index 參數可以開啟自適應哈希索引，數據庫啟動時會自動創建槽數為 innodb_buffer_pool_size/256 個哈希表
可以通過 show engine innodb status 查看當前自適應哈希索引的使用狀況
說明：包括哈希索引的大小，使用情況，每秒使用自適應哈希索引搜索的情況
注：哈希索引只能用來搜索等值的查詢，其他類型不能使用哈希索引
到此，相信大家對“mysql 索引內部實現與算法分析”有了更深的了解，不妨來實際操作一番吧！這里是丸趣 TV 網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
