目錄
- 索引可以用的查找算法
- 一、雜湊演算法
- 二、二叉排序樹
- 三、紅黑樹
- 四、B+樹
- MySQL索引存儲
- 一、myisam引擎（非聚集索引方式）
- 二、INNODB 引擎（聚集索引方式）
筆記來源：源碼學院
索引（Index）是幫助 MySQL 高效擷取資料的資料結構。 常見的查詢算法：順序查找、二分查找、二叉排序樹查找、哈希散列法、分塊查找、平衡多路搜尋樹 B 樹（B-tree）
雜湊演算法(也叫散列)， 就是把任意長度值(Key)通過雜湊演算法變換成固定長度的key位址，通過這個位址進行通路的資料結構。
它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。
這個映射函數叫做散列函數,存放記錄的數組叫做散清單。
比如對于SQL語句：
select * from user where id = 7
很快就可以獲得id=7的實體位址：
hash時間複雜度：O(1)
為什麼MySQL索引沒将hash算法作為主流？
# hash算法很适用于
select * from user where id = 7
# 但是對于以下情況，就力不從心了
select * from user where id < 7
Hash不支援範圍查詢和排序
如果是【平衡二叉樹】，查詢id=7，則查詢了 3 次
但如果平衡二叉樹是以下這種情況【傾斜二叉樹】：
如果查詢id=7，則查詢了 7 次【樹的深度對查找次數有影響】
解決二叉樹的平衡的問題，但是mysql索引依然沒有使用紅黑樹
問題：沒有絕對解決，還是有傾斜現象
真實的資料存在于葉子節點；非葉子節點不存儲真實的資料，隻存儲指引搜尋方向的資料項。
當資料增加時，B+樹會橫向擴容，很難增加樹的深度
select * from user where id = 7
查詢到7，隻需要查詢3次即可
是以B+樹非常适合做索引的底層資料結構【Hash算法有時也會做，因為時間複雜度低】
資料庫的索引會存儲到磁盤
- frm：建立表的語句檔案
- MYD：資料庫資料檔案
- MYI：資料庫索引檔案
因為資料和索引是分開的，是以是非聚集的。
myisam不支援事務
比如以下圖。我們對id和username建立了索引，則我們對id和username的索引都建立了對應的存儲檔案：
- ibd：資料庫資料+索引檔案
INNODB查詢速度不快
比如以下圖。我們對id和username建立了索引
- 第一個IBD索引資料檔案記錄了id和資料
- 第二個IBD索引檔案，如果對username也建立了索引，則記錄的是username的索引和對應的id，為了節省空間，不存儲資料