概述

索引是對數(shù)據(jù)庫表中一列或多列的值進行排序的一種結(jié)構(gòu)，使用索引可快速訪問數(shù)據(jù)庫表中的特定信息。

索引數(shù)據(jù)結(jié)構(gòu)

二叉樹

二叉樹（binary tree）是指樹中節(jié)點的度不大于 2 的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節(jié)點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹

對于數(shù)組 {1,2,3,4,5} 數(shù)據(jù)結(jié)構(gòu)將成為了鏈表

特點：

• 父節(jié)點下面有兩個子節(jié)點。
• 右邊節(jié)點的數(shù)據(jù)大于左邊節(jié)點的數(shù)據(jù)。
  

二叉樹.png

紅黑樹

紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數(shù)據(jù)比如數(shù)字的塊的一種結(jié)構(gòu)。若一棵二叉查找樹是紅黑樹，則它的任一子樹必為紅黑樹。

紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，所以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但對之進行平衡的代價較低， 其平均統(tǒng)計性能要強于 AVL 。

由于每一棵紅黑樹都是一棵二叉排序樹，因此，在對紅黑樹進行查找時，可以采用運用于普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息。

紅黑樹數(shù)據(jù)結(jié)構(gòu)如下圖：

紅黑樹數(shù)據(jù)結(jié)構(gòu).png

特點：

• 紅黑樹是每個結(jié)點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。
• 結(jié)點是紅色或黑色。
• 根結(jié)點是黑色。
• 所有葉子都是黑色。（葉子是NIL結(jié)點）
• 每個紅色結(jié)點的兩個子結(jié)點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結(jié)點）
• 從任一節(jié)結(jié)點其每個葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點。
• 這些約束強制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
• 是性質(zhì)4導致路徑上不能有兩個連續(xù)的紅色結(jié)點確保了這個結(jié)果。最短的可能路徑都是黑色結(jié)點，最長的可能路徑有交替的紅色和黑色結(jié)點。因為根據(jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色結(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。
• 因為紅黑樹是一種特化的二叉查找樹，所以紅黑樹上的只讀操作與普通二叉查找樹相同。

B-Tree

• 葉子結(jié)點具有相同的深度，葉節(jié)點的指針為空
• 所有元素不重復
• 節(jié)點中的數(shù)據(jù)索引從左到右邊遞增排列
  

B樹數(shù)據(jù)結(jié)構(gòu).png

B+Tree

• 非葉子結(jié)點不存儲數(shù)據(jù)，只存儲索引（冗余），可以存放更多的索引
• 葉子結(jié)點包含所有索引字段
• 葉子結(jié)點用指針鏈接，提高區(qū)間訪問的性能（可以提升范圍查找的效率）
  

B+樹數(shù)據(jù)結(jié)構(gòu).png

特點關(guān)鍵字：節(jié)點內(nèi)有序，葉子結(jié)點指針鏈接，非葉子結(jié)點存儲索引（冗余）

查詢mysql 索引的數(shù)據(jù)頁的大小：

mysql> show global status like 'Innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| Innodb_page_size | 16384 |
+------------------+-------+

為什么設(shè)置 16kb 呢？

Hash

• 對索引的 key 進行一次 hash 計算就可以定位出數(shù)據(jù)存儲的位置
• 很多的時候 hash 索引要比 B+ 樹索引更高效
• 僅能滿足 “=” ， “in”  不支持范圍查詢
• 存在 hash 沖突問題
  

Hash 數(shù)據(jù)結(jié)構(gòu).png

索引

InnoDB 索引實現(xiàn)（聚集）

表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個索引結(jié)構(gòu)文件

聚集索引-葉子節(jié)點包含了完整的數(shù)據(jù)記錄

為什么 InnoDb 表必須有主鍵，并且推薦使用整型的自增主鍵？

• 如果沒有設(shè)置索引的話，MySQL 會選擇一個數(shù)據(jù)唯一的列作為主鍵索引， 如果找不這樣的列。會去做創(chuàng)建一個隱藏列類似  rowid。
• 表數(shù)據(jù)文件按照 B+Tree 的數(shù)據(jù)結(jié)構(gòu)維護，在葉子節(jié)點維護的是該行的數(shù)據(jù)。所以必須有主鍵。
• 整型更方便 B+Tree 排序，自增的話，對于數(shù)據(jù)結(jié)構(gòu)的存放更快,  順序存放，不需要進行大量樹的平衡操作。
  

為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點的存儲的是主鍵值？

• 一致性， 讓主鍵索引先成功，然后再去更新非主鍵索引關(guān)系
• 節(jié)省存儲空間。
  

主鍵索引示意圖：

InnoDB 索引實現(xiàn).png

非主鍵索引示意圖圖片

如果查詢的是通過 name = Alice 去查詢的時候：

1. 走非主鍵索引去查詢，查詢完后拿到信息（Alice, 18）。其實這里也是一個非聚簇索引
2. 然后進行回表查詢，再次通過主鍵去查詢做回表查詢。
   

兩個數(shù)據(jù)文件：

.frm 主要是存儲表結(jié)構(gòu)信息

.ibd 主要是存儲索引和數(shù)據(jù)

MyISAM 索引文件（非聚集）

索引文件和數(shù)據(jù)文件是分離的（非聚集）

MyISAM 存儲引擎索引.png

三個數(shù)據(jù)文件：

.frm 數(shù)據(jù)結(jié)構(gòu)文件

.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'                            -- 不命中索引

參考資料

百度百科

總結(jié)

到此這篇關(guān)于MySQL索引數(shù)據(jù)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)MySQL索引數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論