深入解析MySQL索引數(shù)據(jù)結構
概述
索引是對數(shù)據(jù)庫表中一列或多列的值進行排序的一種結構,使用索引可快速訪問數(shù)據(jù)庫表中的特定信息。
索引數(shù)據(jù)結構
二叉樹
二叉樹(binary tree)是指樹中節(jié)點的度不大于 2 的有序樹,它是一種最簡單且最重要的樹。二叉樹的遞歸定義為:二叉樹是一棵空樹,或者是一棵由一個根節(jié)點和兩棵互不相交的,分別稱作根的左子樹和右子樹組成的非空樹;左子樹和右子樹又同樣都是二叉樹
對于數(shù)組 {1,2,3,4,5} 數(shù)據(jù)結構將成為了鏈表
特點:
- 父節(jié)點下面有兩個子節(jié)點。
- 右邊節(jié)點的數(shù)據(jù)大于左邊節(jié)點的數(shù)據(jù)。
二叉樹.png
紅黑樹
紅黑樹是一種特定類型的二叉樹,它是在計算機科學中用來組織數(shù)據(jù)比如數(shù)字的塊的一種結構。若一棵二叉查找樹是紅黑樹,則它的任一子樹必為紅黑樹。
紅黑樹是一種平衡二叉查找樹的變體,它的左右子樹高差有可能大于 1,所以紅黑樹不是嚴格意義上的平衡二叉樹(AVL),但對之進行平衡的代價較低, 其平均統(tǒng)計性能要強于 AVL 。
由于每一棵紅黑樹都是一棵二叉排序樹,因此,在對紅黑樹進行查找時,可以采用運用于普通二叉排序樹上的查找算法,在查找過程中不需要顏色信息。
紅黑樹數(shù)據(jù)結構如下圖:
紅黑樹數(shù)據(jù)結構.png
特點:
- 紅黑樹是每個結點都帶有顏色屬性的二叉查找樹,顏色或紅色或黑色。
- 結點是紅色或黑色。
- 根結點是黑色。
- 所有葉子都是黑色。(葉子是NIL結點)
- 每個紅色結點的兩個子結點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結點)
- 從任一節(jié)結點其每個葉子的所有路徑都包含相同數(shù)目的黑色結點。
- 這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例,這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的,而不同于普通的二叉查找樹。
- 是性質4導致路徑上不能有兩個連續(xù)的紅色結點確保了這個結果。最短的可能路徑都是黑色結點,最長的可能路徑有交替的紅色和黑色結點。因為根據(jù)性質5所有最長的路徑都有相同數(shù)目的黑色結點,這就表明了沒有路徑能多于任何其他路徑的兩倍長。
- 因為紅黑樹是一種特化的二叉查找樹,所以紅黑樹上的只讀操作與普通二叉查找樹相同。
B-Tree
- 葉子結點具有相同的深度,葉節(jié)點的指針為空
- 所有元素不重復
- 節(jié)點中的數(shù)據(jù)索引從左到右邊遞增排列
B樹數(shù)據(jù)結構.png
B+Tree
- 非葉子結點不存儲數(shù)據(jù),只存儲索引(冗余),可以存放更多的索引
- 葉子結點包含所有索引字段
- 葉子結點用指針鏈接,提高區(qū)間訪問的性能(可以提升范圍查找的效率)
B+樹數(shù)據(jù)結構.png
特點關鍵字:節(jié)點內有序,葉子結點指針鏈接,非葉子結點存儲索引(冗余)
查詢mysql 索引的數(shù)據(jù)頁的大小:
mysql> show global status like 'Innodb_page_size'; +------------------+-------+ | Variable_name | Value | +------------------+-------+ | Innodb_page_size | 16384 | +------------------+-------+
為什么設置 16kb 呢?
Hash
- 對索引的 key 進行一次 hash 計算就可以定位出數(shù)據(jù)存儲的位置
- 很多的時候 hash 索引要比 B+ 樹索引更高效
- 僅能滿足 “=” , “in” 不支持范圍查詢
- 存在 hash 沖突問題
Hash 數(shù)據(jù)結構.png
索引
InnoDB 索引實現(xiàn)(聚集)
表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個索引結構文件
聚集索引-葉子節(jié)點包含了完整的數(shù)據(jù)記錄
為什么 InnoDb 表必須有主鍵,并且推薦使用整型的自增主鍵?
- 如果沒有設置索引的話,MySQL 會選擇一個數(shù)據(jù)唯一的列作為主鍵索引, 如果找不這樣的列。會去做創(chuàng)建一個隱藏列類似 rowid。
- 表數(shù)據(jù)文件按照 B+Tree 的數(shù)據(jù)結構維護,在葉子節(jié)點維護的是該行的數(shù)據(jù)。所以必須有主鍵。
- 整型更方便 B+Tree 排序,自增的話,對于數(shù)據(jù)結構的存放更快, 順序存放,不需要進行大量樹的平衡操作。
為什么非主鍵索引結構葉子節(jié)點的存儲的是主鍵值?
- 一致性, 讓主鍵索引先成功,然后再去更新非主鍵索引關系
- 節(jié)省存儲空間。
主鍵索引示意圖:
InnoDB 索引實現(xiàn).png
非主鍵索引示意圖圖片
如果查詢的是通過 name = Alice 去查詢的時候:
- 走非主鍵索引去查詢,查詢完后拿到信息(Alice, 18)。其實這里也是一個非聚簇索引
- 然后進行回表查詢,再次通過主鍵去查詢做回表查詢。
兩個數(shù)據(jù)文件:
.frm 主要是存儲表結構信息
.ibd 主要是存儲索引和數(shù)據(jù)
MyISAM 索引文件(非聚集)
索引文件和數(shù)據(jù)文件是分離的(非聚集)
MyISAM 存儲引擎索引.png
三個數(shù)據(jù)文件:
.frm 數(shù)據(jù)結構文件
.myd 文件主要是存儲數(shù)據(jù)
.myi 文件主要是存儲索引信息
聚集索引和非聚集索引
特征:
聚集/非聚集主要是索引文件是否和數(shù)據(jù)文件在一起。
查詢效率上來說聚集索引不會跨文件查詢效率會更加快。
聯(lián)合/復合索引
多個字段組織成一個共同的索引
組合索引.png
最左前綴原理為什么這樣來使用?
索引的數(shù)據(jù)是被排序的,如果跳過字段的話是無法被使用的。
示例:
where name = 'Jeff' and age = 22 -- 命中索引 where age = 30 and postatin='manager' -- 不命中索引 where postation = 'dev' -- 不命中索引
參考資料
百度百科
總結
到此這篇關于MySQL索引數(shù)據(jù)結構的文章就介紹到這了,更多相關MySQL索引數(shù)據(jù)結構內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
MySQL事務日志(redo?log和undo?log)的詳細分析
innodb事務日志包括redo?log和undo?log,redo?log是重做日志,提供前滾操作,undo?log是回滾日志,提供回滾操作,下面這篇文章主要給大家介紹了關于MySQL事務日志(redo?log和undo?log)的詳細分析,需要的朋友可以參考下2022-04-04mysql創(chuàng)建數(shù)據(jù)庫,添加用戶,用戶授權實操方法
在本篇文章里小編給大家整理的是關于mysql創(chuàng)建數(shù)據(jù)庫,添加用戶,用戶授權實操方法相關知識點,需要的朋友們學習下。2019-10-10mysql-8.0.35-winx64?zip版安裝教程(附圖文)
許多人在學習過程中經常因使用不當將MySQL數(shù)據(jù)庫搞崩潰,這篇文章主要給大家介紹了關于mysql-8.0.35-winx64?zip版安裝教程的相關資料,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2024-01-01