Mysql索引結構&頁&聚集索引&非聚集索

[toc]

摘要

第一部分主要從數(shù)據(jù)結構及算法理論層面討論MySQL數(shù)據(jù)庫索引的數(shù)理基礎。
第二部分結合MySQL數(shù)據(jù)庫中MyISAM和InnoDB數(shù)據(jù)存儲引擎中索引的架構實現(xiàn)討論聚集索引、非聚集索引及覆蓋索引等話題。

索引

索引概述

MySQL官方對索引的定義為：索引（index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結構（有序）。在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護者滿足特定查找算法的數(shù)據(jù)結構，這些數(shù)據(jù)結構以某種方式引用（指向）數(shù)據(jù)， 這樣就可以在這些數(shù)據(jù)結構上實現(xiàn)高級查找算法，這種數(shù)據(jù)結構就是索引。

索引優(yōu)勢劣勢

  • 優(yōu)勢
    • 類似于書籍的目錄索引，提高數(shù)據(jù)檢索的效率，降低數(shù)據(jù)庫的IO成本。
    • 通過索引列對數(shù)據(jù)進行排序，降低數(shù)據(jù)排序的成本，降低CPU的消耗。
  • 劣勢
    • 實際上索引也是一張表，該表中保存了主鍵與索引字段，并指向實體類的記錄，所以索引列也是要占用空間的。
    • 雖然索引大大提高了查詢效率，同時卻也降低更新表的速度，如對表進行INSERT、UPDATE、DELETE。因為更新表時，MySQL 不僅要保存數(shù)據(jù)，還要保存一下索引文件每次更新添加了索引列的字段，都會調整因為更新所帶來的鍵值變化后的索引信息

索引結構

索引是在MySQL的存儲引擎層中實現(xiàn)的，而不是在服務器層實現(xiàn)的。所以每種存儲引擎的索引都不一定完全相同，也不是所有的存儲引擎都支持所有的索引類型的。MySQL目前提供了以下4種索引：

  • BTREE 索引 ： 最常見的索引類型，大部分索引都支持 B 樹索引。
  • HASH 索引：只有Memory引擎支持 ， 使用場景簡單 。
  • R-tree 索引（空間索引）：空間索引是MyISAM引擎的一個特殊索引類型，主要用于地理空間數(shù)據(jù)類型，通常使用較少，不做特別介紹。
  • Full-text （全文索引） ：全文索引也是MyISAM的一個特殊索引類型，主要用于全文索引，InnoDB從
    Mysql5.6版本開始支持全文索引
    [圖片上傳失敗...(image-2fd524-1591539893523)]
  • 平常所說的索引，如果沒有特別指明，都是指B+樹（多路搜索樹，并不一定是二叉的）結構組織的索引。其中聚集索引、復合索引、前綴索引、唯一索引默認都是使用 B+tree 索引，統(tǒng)稱為 索引；

聚集索引 復合索引區(qū)別：
聚簇索引：將數(shù)據(jù)存儲與索引放到了一塊，索引結構的葉子節(jié)點保存了行數(shù)據(jù)
非聚簇索引：將數(shù)據(jù)與索引分開存儲，索引結構的葉子節(jié)點指向了數(shù)據(jù)對應的位置

BTREE 結構

BTree又叫多路平衡搜索樹，一顆m叉的BTree特性如下：

  • 樹中每個節(jié)點最多包含m個孩子。
  • 除根節(jié)點與葉子節(jié)點外，每個節(jié)點至少有[ceil(m/2)]個孩子。
  • 若根節(jié)點不是葉子節(jié)點，則至少有兩個孩子。
  • 所有的葉子節(jié)點都在同一層。
  • 每個非葉子節(jié)點由n個key與n+1個指針組成，其中[ceil(m/2)-1] <= n <= m-1

以5叉BTree為例，key的數(shù)量：公式推導[ceil(m/2)-1] <= n <= m-1。所以 2 <= n <=4 。當n>4時，中間節(jié)點分裂到
父節(jié)點，兩邊節(jié)點分裂。
插入 C N G A H E K Q M F W L T Z D P R X Y S 數(shù)據(jù)為例。
動畫演示
演變過程如下，可以通過上面的網(wǎng)站走一下這個過程：
1). 插入前4個字母 C N G A
2). 插入H，n>4，中間元素G字母向上分裂到新的節(jié)點
3). 插入E，K，Q不需要分裂
4). 插入M，中間元素M字母向上分裂到父節(jié)點G
5). 插入F，W，L，T不需要分裂
6). 插入Z，中間元素T向上分裂到父節(jié)點中
7). 插入D，中間元素D向上分裂到父節(jié)點中。然后插入P，R，X，Y不需要分裂
8). 最后插入S，NPQR節(jié)點n>5，中間節(jié)點Q向上分裂，但分裂后父節(jié)點DGMT的n>5，中間節(jié)點M向上分裂

在這里插入圖片描述

  • BTREE樹 和 二叉樹相比，查詢數(shù)據(jù)的效率更高， 因為對于相同的數(shù)據(jù)量來說，BTREE的層級結構比二叉樹小，因此搜索速度快。

B+TREE 結構

B+Tree為BTree的變種，B+Tree與BTree的區(qū)別為：
1). n叉B+Tree最多含有n個key，而BTree最多含有n-1個key。
2). B+Tree的葉子節(jié)點保存所有的key信息，依key大小順序排列。
3). 所有的非葉子節(jié)點都可以看作是key的索引部分
通過下面的圖，可以非常直觀的看出來二者的差異：
[圖片上傳失敗...(image-6caab0-1591539893523)]


B+樹

MySQL中的B+Tree

頁

它是InnoDB管理存儲空間的基本單位，一個頁的大小一般是16KB。InnoDB為了不同的目的而設計了許多種不同類型的頁，比如存放表空間頭部信息的頁，存放Insert Buffer信息的頁，存放INODE信息的頁，存放undo日志信息的頁等等等等。


頁結構

頁

插入數(shù)據(jù)過程
  • 一個B+樹節(jié)點就是一個頁（16KB）
  • B+樹葉子節(jié)點前后形成雙向鏈表

  • 頁與頁之間是雙向鏈表頁里面的數(shù)據(jù)是單向鏈表 如圖所示:


    在這里插入圖片描述

索引分類

  1. 單值索引 ：即一個索引只包含單個列，一個表可以有多個單列索引
  2. 唯一索引 ：索引列的值必須唯一，但允許有空值
  3. 復合索引 ：即一個索引包含多個列

索引語法

  • 創(chuàng)建索引

CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name
[USING index_type]
ON tbl_name(index_col_name,...)
示例 ：
CREATE INDEX index_name ON table_name (column_list)
CREATE UNIQUE INDEX index_name ON table_name (column_list)

  • 追加索引

ALTER TABLE用來創(chuàng)建普通索引、UNIQUE索引或PRIMARY KEY索引。
ALTER TABLE table_name ADD INDEX index_name (column_list)
ALTER TABLE table_name ADD UNIQUE (column_list)
ALTER TABLE table_name ADD PRIMARY KEY (column_list)

  • 查看索引

show index from table_name;

  • 刪除索引

DROP INDEX index_name ON tbl_name;

索引設計原則

索引的設計可以遵循一些已有的原則，創(chuàng)建索引的時候請盡量考慮符合這些原則，便于提升索引的使用效率，更高
效的使用索引。

  1. 對查詢頻次較高，且數(shù)據(jù)量比較大的表建立索引
  2. 索引字段的選擇，最佳候選列應當從where子句的條件中提取，如果where子句中的組合比較多，那么應當挑選最常用、過濾效果最好的列的組合
  3. 使用唯一索引，區(qū)分度越高，使用索引的效率越高。
  4. 索引可以有效的提升查詢數(shù)據(jù)的效率，但索引數(shù)量不是多多益善，索引越多，維護索引的代價自然也就水漲船高。對于插入、更新、刪除等DML操作比較頻繁的表來說，索引過多，會引入相當高的維護代價，降低DML操作的效率，增加相應操作的時間消耗。另外索引過多的話MySQL也會犯選擇困難病，雖然最終仍然會找到一個可用的索引，但無疑提高了選擇的代價。
  5. 使用短索引，索引創(chuàng)建之后也是使用硬盤來存儲的，因此提升索引訪問的I/O效率，也可以提升總體的訪問效率。假如構成索引的字段總長度比較短，那么在給定大小的存儲塊內可以存儲更多的索引值，相應的可以有效的提升MySQL訪問索引的I/O效率。
  6. 利用最左前綴，N個列組合而成的組合索引，那么相當于是創(chuàng)建了N個索引，如果查詢時where子句中使用了組成該索引的前幾個字段，那么這條查詢SQL可以利用組合索引來提升查詢效率。

聚觸索引 & 非聚觸索引

聚集索引與非聚集索引的區(qū)別是：葉節(jié)點是否存放一整行記錄
InnoDB 主鍵使用的是聚簇索引和輔助索引，MyISAM 不管是主鍵索引，還是二級索引使用的都是非聚簇索引。
下圖形象說明了聚簇索引表(InnoDB)和非聚簇索引(MyISAM)的區(qū)別：


索引區(qū)別

  • 對于聚簇索引表來說（左圖），表數(shù)據(jù)是和主鍵一起存儲的，主鍵索引的葉結點存儲行數(shù)據(jù)(包含了主鍵值)，二級索引的葉結點存儲行的主鍵值。使用的是B+樹作為索引的存儲結構，非葉子節(jié)點都是索引關鍵字，但非葉子節(jié)點中的關鍵字中不存儲對應記錄的具體內容或內容地址。葉子節(jié)點上的數(shù)據(jù)是主鍵與具體記錄(數(shù)據(jù)內容)。

  • 對于非聚簇索引表來說（右圖），表數(shù)據(jù)和索引是分成兩部分存儲的，主鍵索引和二級索引存儲上沒有任何區(qū)別。使用的是B+樹作為索引的存儲結構，所有的節(jié)點都是索引，葉子節(jié)點存儲的是索引+索引對應的記錄的數(shù)據(jù)。

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

    • 需要取出一定范圍內的數(shù)據(jù)時，用聚簇索引也比用非聚簇索引好。
    • 當通過聚簇索引查找目標數(shù)據(jù)時理論上比非聚簇索引要快，因為非聚簇索引定位到對應主鍵時還要多一次目標記錄尋址,即多一次I/O。
    • 使用覆蓋索引掃描的查詢可以直接使用頁節(jié)點中的主鍵值。

  • 聚簇索引的缺點

    • 插入速度嚴重依賴于插入順序，按照主鍵的順序插入是最快的方式，否則將會出現(xiàn)頁分裂，嚴重影響性能。因此，對于InnoDB表，我們一般都會定義一個自增的ID列為主鍵。
    • 更新主鍵的代價很高，因為將會導致被更新的行移動。因此，對于InnoDB表，我們一般定義主鍵為不可更新。
    • 二級索引（輔助索引）訪問需要兩次索引查找，第一次找到主鍵值，第二次根據(jù)主鍵值找到行數(shù)據(jù)。二級索引的葉節(jié)點存儲的是主鍵值，而不是行指針（非聚簇索引存儲的是指針或者說是地址），這是為了減少當出現(xiàn)行移動或數(shù)據(jù)頁分裂時二級索引的維護工作，但會讓二級索引占用更多的空間。
    • 采用聚簇索引插入新值比采用非聚簇索引插入新值的速度要慢很多，因為插入要保證主鍵不能重復，判斷主鍵不能重復，采用的方式在不同的索引下面會有很大的性能差距，聚簇索引遍歷所有的葉子節(jié)點，非聚簇索引也判斷所有的葉子節(jié)點，但是聚簇索引的葉子節(jié)點除了帶有主鍵還有記錄值，記錄的大小往往比主鍵要大的多。這樣就會導致聚簇索引在判定新記錄攜帶的主鍵是否重復時進行昂貴的I/O代價。

參考：

你的鼓勵也是我創(chuàng)作的動力

打賞地址

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內容