天天看點
傳回

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

1 資料結構及算法基礎

1.1 索引到底是什麼？

官方定義：索引（Index）是幫助MySQL高效擷取資料的資料結構，即索引是資料結構。

其出現就是為了提高資料查詢效率，就像書的目錄。

既然是查詢，就主要需要從查詢算法角度優化。

  • 最基本的查詢算法 順序查找 （linear search），複雜度為O(n)的算法在資料量大時是糟糕的。
  • 更優秀的查找算法，如二分查找要求被檢索資料有序，二叉樹查找隻能應用于 二叉查找樹 ，但

    資料本身的組織結構不可能完全滿足各種資料結構

是以，在資料之外，資料庫系統還維護着滿足特定查找算法的資料結構，這些資料結構以某種方式引用（指向）資料，這樣就可以在這些資料結構上實作進階查找算法這種ADT，就是索引。

  • 一種可能的索引方式
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

左邊是資料表，兩列14條記錄，最左邊是資料記錄的實體位址。

為加快

Col2

的查找，可維護一個右邊所示二叉查找樹，每個節點分别包含索引鍵值及一個指向對應資料記錄實體位址的指針，這樣就可以運用二叉查找在O(log2 N)内取到相應資料。

但實際資料庫系統幾乎沒有使用二叉查找樹或其進化品種

紅黑樹

（red-black tree）實作

1.4 主存存取原理

計算機使用的主存基本都是随機讀寫存儲器（RAM），抽象出一個十分簡單的存取模型來說明RAM的工作原理

從抽象角度看，主存是一系列的存儲單元組成的矩陣，每個存儲單元存儲固定大小的資料

每個存儲單元有唯一的位址，現代主存的編址規則比較複雜，這裡将其簡化成一個二維位址：通過一個行位址和一個列位址可以唯一定位到一個存儲單元

  • 存取過程

    當系統需要讀取主存時，将位址信号通過位址總線傳給主存，主存讀到位址信号後，解析信号并定位到指定存儲單元，然後将此存儲單中繼資料放到資料總線，供其它部件讀取

  • 寫主存

    過程類似，系統将要寫入單元位址和資料分别放在位址總線和資料總線上，主存讀取兩個總線的内容，做相應的寫操作

這裡可以看出，主存存取的時間僅與存取次數呈線性關系，因為不存在機械操作，兩次存取的資料的“距離”不會對時間有任何影響，例如，先取A0再取A1和先取A0再取D3的時間消耗是一樣的

1.5 磁盤存取原理

索引一般以檔案形式存儲在磁盤上，索引檢索需要磁盤I/O。與主存不同，磁盤I/O存在機械消耗，是以磁盤I/O時間消耗巨大。

磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動（各磁盤必須同步轉動）

在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的内容。磁頭不能轉動，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）

盤片被劃分成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區，每個扇區是磁盤的最小存儲單元。為了簡單起見，我們下面假設磁盤隻有一個盤片和一個磁頭。

當需要從磁盤讀取資料時，系統會将資料邏輯位址傳給磁盤，磁盤的控制電路按照尋址邏輯将邏輯位址翻譯成實體位址，即确定要讀的資料在哪個磁道，哪個扇區

為了讀取這個扇區的資料，需要将磁頭放到這個扇區上方，為了實作這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然後磁盤旋轉将目标扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間

1.6 局部性原理與磁盤預讀

由于存儲媒體特性，磁盤本身存取就比主存慢，再加上機械運動耗費，磁盤存取速度往往是主存的幾百萬分之一，是以要提高效率，必須減少磁盤I/O。

為了達到這個目的，磁盤往往也不是嚴格按需讀取，而是每次都會預讀，即使隻需要一個位元組，磁盤也會從這個位置開始，順序向後再讀取一定長度的資料放入記憶體。

這樣做的理論依據是計算機科學中著名的局部性原理：

當一個資料被用到時，其附近的資料也通常會馬上被使用

，

程式運作期間所需要的資料通常比較集中

。

由于磁盤順序讀取的效率很高（無需尋道時間，隻需很少的旋轉時間），是以對于具有局部性的程式來說，預讀可以提高I/O效率。

預讀的長度一般為頁（page）的整數倍

。innodb 預設一次讀取 16k 。

頁是存儲器的邏輯塊，os往往将主存和磁盤存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁（許多 os 的頁大小一般為4k），主存和磁盤以頁為機關交換資料。

當程式要讀取的資料不在主存中時，會觸發缺頁異常，系統會向磁盤發出讀盤信号，磁盤會找到資料的起始位置并向後連續讀取一頁或幾頁載入記憶體中，然後異常傳回，程式繼續運作。

1.7 性能分析

一般使用磁盤I/O次數評價索引結構的優劣

1.7.1 為什麼不用平衡二叉樹？

平衡二叉樹隻有兩個分支，而B+樹的分支≥2；

B+樹的層數隻會小于平衡二叉樹，層數越少，在查詢時所需要的 I/O 硬碟通路越少，查詢速度相對更快，提高了對系統資源的使用率。

1.7.2 為什麼不用紅黑樹？

h明顯要深的多。由于邏輯上很近的節點（父子）實體上可能很遠，無法利用局部性，是以紅黑樹的I/O漸進複雜度也為O(h)，效率明顯比B-Tree差很多

B+Tree更适合外存索引，原因和内節點出度d有關

從上面分析可以看到，

d越大索引的性能越好

出度的上限取決于節點内key和data的大小

：

dmax=floor(pagesize/(keysize+datasize+pointsize))

floor表示向下取整。由于B+Tree内節點去掉了data域，是以可以擁有更大的出度，更好的性能.

1.7.3 B Tree

定義資料記錄為一個二進制組[key, data]

  • key為記錄的K值，對于不同資料記錄，key互不相同
  • data為資料記錄除key外的資料

特點

  • d為大于1的一個正整數，為B-Tree的度
  • h為一個正整數，為B-Tree的高度
  • 每個非葉節點由n-1個key和n個指針組成，其中d<=n<=2d
  • 每個葉節點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針，葉節點的指針均為null
  • 所有葉節點具有相同深度，等于樹高h
  • key和指針互相間隔，節點兩端是指針
  • 一個節點中的key從左到右非遞減排列
  • 所有節點組成樹結構
  • 每個指針要麼為null，要麼指向另外一個節點
  • 如果某個指針在節點node最左邊且不為null，則其指向節點的所有key小于>v(key1),v(key1)為node的第一個key的值
  • 如果某個指針在節點node最右邊且不為null，則其指向節點的所有key大于v(keym),v(keym)為node的最後一個key的值。
  • 如果某個指針在節點node的左右相鄰key分别是keyi,keyi+1且不為null，則其指向節點的所有key小于v(keyi+1)且大于v(keyi)

由于B Tree的特性，按key檢索資料的算法非常直覺

  • 首先從根節點二分查找
  • 如果找到則傳回對應節點的data
  • 否則對相應區間的指針指向的節點遞歸進行查找
  • 直到找到目标節點/null指針，查找成功/失敗 
bTreeSearch(node, key) {
    if(node == null) return null;
    foreach(node.key) {
        if(node.key[i] == key) return node.data[i];
            if(node.key[i] > key) return bTreeSearch(point[i]->node);
    }
    return bTreeSearch(point[i+1]->node);
}
data = bTreeSearch(root, my_key);

關于B-Tree有一系列有趣的性質，例如一個度為d的B-Tree，設其索引N個key，則其樹高h的上限為

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

檢索一個key，其查找節點個數的漸進時間複雜度為

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

從這點可以看出，B Tree是一個非常有效率的索引資料結構。

檢索一次最多需要通路h個節點。資料庫系統的設計者巧妙利用了磁盤預讀原理（磁盤資料存儲是采用塊的形式存儲的，每個塊的大小為4K，每次I/O進行資料讀取時，同一個磁盤塊的資料可以一次性讀取出來），将一個節點的大小設為塊的整數倍16K，這樣每個磁盤塊隻需一次I/O即可完全載入記憶體。

為達到該目的，在實際實作B-Tree還需要使用如下技巧：

  1. 每次建立節點時，直接申請一個頁的空間，保證一個節點實體上也存儲在一個頁裡，而且計算機存儲配置設定都是按頁對齊，就實作了一個node隻需一次I/O
  2. B-Tree中一次檢索最多需要h-1次I/O（根節點是常駐記憶體的），漸進複雜度為O(h)=O(logdN)

以InnoDB的一個整數字段索引為例，N差不多是1200。樹高是4時，可存

1200^3=17億

考慮到根的資料塊總在記憶體，一個10億行的表上一個整數字段的索引，查找一個值最多隻需要通路3次磁盤。其實，樹的第二層也有很大機率在記憶體中，那麼通路磁盤的平均次數就更少了。

綜上所述，用B-Tree作為索引結構效率是非常高的。但是其内部的非葉節點也存儲了 data 資料，是以一個節點裡也存不了多少資料。

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

1.7.4 B+樹對B樹的優勢差異

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

與B Tree相比，B+Tree有以下不同點：

  • 每個節點的指針上限為2d
  • 内節點隻存key
  • 葉節點不存指針,葉節點指向被索引的資料而不是其他葉節點
    • innodb中,指向的是主鍵
    • myshaym中指向的是資料的實體位址

由于并不是所有節點都具有相同的域，是以B+Tree中葉節點和内節點一般大小不同

這點與B Tree不同，雖然B Tree中不同節點存放的key和指針可能數量不一緻，但是每個節點的域和上限是一緻的，是以在實作中B Tree往往對每個節點申請同等大小的空間。

結構

  • B+ 樹的非葉節點不存儲資料，且所有資料節點之間指針串聯（即連結清單）。B+Tree的每個葉節點增加一個指向相鄰葉節點指針，形成帶有順序通路指針的B+Tree。此優化的目的是提高區間通路的性能，例如要查詢key為從18到49的所有資料記錄，當找到18後，隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點，極大提高區間查詢效率
  • B 樹子結點帶資料，且兄弟節點之間無指針串聯

查詢性能

最簡單的對比測試，假設範圍查詢 [0,N-1] ：

  • B+ 樹，隻需要确定範圍查詢的邊界節點，然後周遊即可

    時間複雜度粗略算做

    2logN + N

     (2logN：兩個範圍邊界值的查找)

  • B 樹可能就需要一個個查找

    B 樹就是

    NlogN

範圍越大，查詢性能差異越明顯。

為什麼不用 B*樹？

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

B*樹是B+樹的變種：

  1. 關鍵字個數限制問題，B+樹初始化的關鍵字初始化個數是cei(m/2)，b樹的初始化個數為（cei(2/3m)）
  2. B+樹節點滿時就會分裂，而B*樹節點滿時會檢查兄弟節點是否滿（因為每個節點都有指向兄弟的指針），如果兄弟節點未滿則向兄弟節點轉移關鍵字，如果兄弟節點已滿，則從目前節點和兄弟節點各拿出1/3的資料建立一個新的節點出來

2 索引的實作

索引屬于存儲引擎部分，不同存儲引擎索引實作方式不同。本文隻讨論MyISAM和InnoDB兩個存儲引擎的索引實作方式。

2.1 MyISAM索引

使用B+Tree作為索引結構，葉節點data域存放資料記錄的位址

  • MyISAM索引的原理圖
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

設Col1為主鍵，則上圖是一個MyISAM表的主索引（Primary key），可見MyISAM的索引檔案僅儲存資料記錄的位址。

MyISAM的主/輔索引在結構上無任何差別，隻是主索引要求

key唯一

，輔索引

key可重複

如果在Col2上建立一個輔索引

  • Col2上建立的輔索引
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

同樣也是一顆B+Tree，data域儲存資料記錄的位址。

是以，MyISAM中索引檢索的算法為首先按照B+Tree搜尋算法搜尋索引，如果指定的Key存在，則取出其data域的值，然後以data域的值為位址，讀取相應資料記錄。

MyISAM的索引方式也叫“非聚集”，是為了與InnoDB的聚集索引差別。

注意 聚集 = 聚簇

2.2 InnoDB 索引

雖然InnoDB也使用B+Tree作為索引結構，但具體實作方式卻與MyISAM截然不同

InnoDB的資料檔案本身就是索引檔案

  • MyISAM

    索引檔案和資料檔案分離，索引僅儲存資料的位址

  • InnoDB

    表資料檔案本身就是按B+Tree組織的一個索引結構，該樹的葉節點data域儲存了完整的資料記錄。

    索引的key：資料表的主鍵，是以InnoDB表資料檔案本身就是主索引。

  • InnoDB主索引（也是資料檔案）
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

InnoDB的資料檔案本身要按主鍵聚集，是以InnoDB要求表必須有主鍵（MyISAM可無），如果沒有顯式指定，則MySQL會自動選擇一個可以唯一辨別資料記錄的列作為主鍵。

不存在這種列，則MySQL自動為InnoDB表生一個隐含字段作為主鍵，這個字段長度為6個位元組，類型為長整形

InnoDB的輔索引data域存儲相應記錄主鍵的值而非位址

即InnoDB的所有輔助索引都引用主鍵作為data域。

  • 定義在Col3上的一個輔索引
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

這裡以英文字元的ASCII碼作為比較準則

聚集索引這種實作方式使得按主鍵的搜尋十分高效，但是輔助索引搜尋需要檢索兩遍索引：

  • 首先檢索輔助索引獲得主鍵
  • 然後用主鍵到主索引中檢索獲得記錄

知道了InnoDB的索引實作後，就很容易明白為什麼不建議使用過長的字段作為主鍵，因為所有輔索引都引用主索引，過長的主索引會令輔索引變得過大

再如，用非單調的字段作為主鍵在InnoDB中不是個好主意，因為InnoDB資料檔案本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時資料檔案為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是一個很好的選擇。

InnoDB表都根據主鍵順序以索引形式存放，該存儲方式的表稱為索引組織表。

而InnoDB又使用的B+樹索引模型，是以資料都是存儲于B+樹。

每一個索引在InnoDB裡面就對應一棵B+樹。

主鍵列id，字段k，在k上有索引的建表語句

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

表中R1~R5的(id,k)值分别為(100,1)、(200,2)、(300,3)、(500,5)、(600,6)

  • 兩棵樹的示意圖，即InnoDB的索引組織結構
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

根據葉節點内容，索引類型分為

主鍵索引(聚簇索引)

InnoDB的主鍵索引也稱聚簇索引、聚集索引（clustered index）。主鍵索引的葉節點存整行資料。

聚簇索引并非一種單獨的索引類型，而是一種

資料存儲方式

細節依賴其實作方式，但InnoDB 的聚簇索引實際上在同一個結構中

儲存了B-Tree索引和資料行

，是對磁盤上實際資料重新組織以按指定的一個或多個列的值排序的算法。

每個 InnoDB 表都有一個稱為聚集索引的特殊索引，用于存儲行資料。通常，聚集索引與主鍵同義。為了從查詢、插入和其他資料庫操作中獲得最佳性能，了解 InnoDB 如何使用聚集索引來優化常見的查找和 DML 操作非常重要。

  • 在表上定義主鍵時，InnoDB 将其用作聚簇索引。應該為每個表定義一個主鍵。若沒有邏輯唯一且非空的列或列集使用主鍵，請添加自增列。自增列值是唯一的，并在插入新行時自動添加
  • 若未定義主鍵，則 InnoDB 使用第一個 UNIQUE 索引，所有鍵列都定義為 NOT NULL 作為聚集索引。
  • 若表沒有主鍵或合适的唯一索引，InnoDB 會在包含行 ID 值的合成列上生成一個名為 GEN_CLUST_INDEX 的隐藏聚集索引。行按 InnoDB 配置設定的行 ID 排序。行 ID 是一個 6 位元組的字段，随着插入新行而單調增加。是以，按行 ID 排序的行在實體上是按插入順序排列的。

存儲資料的順序和索引順序一緻。

一般情況下主鍵會預設建立聚簇索引，

一張表隻允許存在一個聚簇索引

當表有聚簇索引，資料實際存在索引葉子頁（leaf page）中。

  • 聚簇

     資料行和相鄰的鍵值交錯的存儲在一起，InnoDb通過主鍵聚集資料。

    因無法同時把資料行存放在兩個不同地方，是以在一個表隻能有一個聚簇索引

     （不過，覆寫索引可以模拟多個聚簇索引）。
  • 若未定義主鍵，InnoDB 會選擇一個唯一的非空索引代替
  • 若無這樣的索引，InnoDB 會隐式定義一個主鍵來作為聚簇索引
  • InnoDB值聚集在同一個頁面中的記錄，包含相鄰鍵值的頁面可能會相距很遠。

聚集索引如何加快查詢速度

通過聚集索引通路一行很快，因為索引搜尋直接指向包含行資料的頁面。若表很大，與使用與索引記錄不同的頁面存儲行資料的存儲組織相比，聚簇索引體系結構通常可以節省磁盤 I/O。

二級索引與聚集索引的關系

聚集索引以外的索引稱為二級索引。在 InnoDB 中，二級索引中的每條記錄都包含該行的主鍵列，以及為二級索引指定的列。 InnoDB 使用這個主鍵值來搜尋聚集索引中的行。

如果主鍵很長，二級索引會占用更多的空間，是以主鍵短是有利的。

非主鍵索引

也叫非聚簇索引、輔助索引、二級索引secondary index）。

非主鍵索引的葉節點是主鍵值。

主鍵索引 V.S 普通索引的查詢

  • select * from T where ID=500，主鍵查詢，隻需搜ID這棵B+樹
  • select * from T where k=5，普通索引查詢，需先搜k索引樹，得到ID的值為500，再到ID索引樹搜尋（回表）。

回表：InnoDB在普通索引a上查到主鍵id的值後，再根據一個個主鍵id的值到主鍵索引上去查整行資料的過程。

非主鍵索引的查詢需要多掃描一棵索引樹。是以

盡量使用主鍵查詢

，減少回表。

InnoDB和MyISAM是如何存儲下面的這個表的

CREATE TABLE layout_test(
　　　　col1 int not null,
　　　　col2 int not null,
 　　　 primary key (col1),
　　　　key(col2)
);

假設該表的主鍵取值為1~10000，按随機順序插入，并使用

OPTIMIZE TABLE

指令優化。

即資料在磁盤的存儲方式已最優，但進行的順序是随機的。

列col2的值時從1~100之間随機指派，是以有很多重複值。

MyISAM 資料分布

MyIsam按資料插入的順序存儲在磁盤。實際上，MyISAM 中主鍵索引和其他索引在結構上沒有什麼不同。主鍵索引就是一個名為PRIMARY的唯一非空索引。

InnoDB 的資料分布

而InnoDB支援聚簇索引，在InnoDB中，聚簇索引“是”表，不像myISAM那樣需要獨立的行存儲。

聚簇索引優點

  • 把相關資料儲存在一起

    例如，實作電子郵箱時，可以根據使用者id來聚集資料，這樣隻需要從磁盤讀取少數資料頁，就能擷取某個使用者的全部郵件。若未使用聚簇索引，則每封郵件都可能導緻一次I/O。

  • 資料通路更快

    聚簇索引将索引和資料儲存在同一B-Tree，從聚簇索引中擷取資料通常比非聚簇索引中快

  • 覆寫索引掃描的查詢可以直接使用頁節點中的主鍵值

聚簇索引缺點

聚簇索引最大限度提高了I/O密集型應用性能，但若資料全存記憶體，則通路順序就沒那麼重要，聚簇索引也沒啥優勢了。

  • 插入速度嚴重依賴插入的順序

    按主鍵的順序插入是加載資料到innodb表中速度最快的。

    但若不是按主鍵順序，則加載後最好使用OPTIMIZE TABLE重新組織表。

  • 更新聚簇索引的代價高

    因為會強制InooDB将每個更新的資料移動到新位置。

基于聚簇索引的表在插入行，或主鍵被更新導緻需要移動行時，可能産生頁分裂（page split）。

當行的主鍵值要求必須将該行插入到某個滿頁時。存儲引擎會将該頁分裂成兩個頁面來容納該行，這就是一次頁分裂。頁分裂會導緻表占用更多存儲空間。

聚簇索引可能導緻全表掃描變慢，尤其是行比較稀疏，或由于頁分裂導緻資料存儲不連續時。

二級索引（非聚簇索引）可能比想象的要更大，因為在二級索引的子節點包含了最優一個幾點可能讓人有些疑惑

  • 為什麼二級索引需要兩次索引查找？

二級索引中儲存的“行指針”的本質：不是實體位址的指針，而是行的主鍵值。是以通過二級索引查找行，引擎需要找到二級索引的子節點獲得對應主鍵值，然後根據該值去聚簇索引找到對應行。

出現重複工作：兩次B-Tree查找，而非一次。對于InnoDB，自适應哈希索引能夠減少這樣重複。

《資料庫原理》解釋聚簇索引和非聚簇索引差別：

  • 聚簇索引的葉節點就是資料節點
  • 非聚簇索引的葉節點仍是索引節點，隻不過有指向對應資料塊的指針

MYISAM和INNODB兩種引擎的索引結構。

  • 原始資料
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護
  • MyISAM資料存儲
MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

MYISAM按列值與行号組織索引，葉子節點儲存的是指向存放資料的實體塊的指針。

MYISAM引擎的索引檔案（.MYI）和資料檔案(.MYD)是互相獨立的。

而InnoDB按聚簇索引存儲資料，存儲資料的結構如下：

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

注：聚簇索引中的每個葉子節點包含主鍵值、事務ID、復原指針(rollback pointer用于事務和MVCC）和餘下的列(如col2)。

INNODB的二級索引與主鍵索引有很大的不同。InnoDB的二級索引的葉子包含主鍵值，而不是行指針(row pointers)，這減小了移動資料或者資料頁面分裂時維護二級索引的開銷，因為InnoDB不需要更新索引的行指針。其結構大緻如下：

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

INNODB和MYISAM的主鍵索引與二級索引的對比：

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

InnoDB的的二級索引的葉子節點存放的是KEY字段加主鍵值。是以，通過二級索引查詢首先查到是主鍵值，然後InnoDB再根據查到的主鍵值通過主鍵索引找到相應的資料塊。而MyISAM的二級索引葉子節點存放的還是列值與行号的組合，葉子節點中儲存的是資料的實體位址。是以可以看出MYISAM的主鍵索引和二級索引沒有任何差別，主鍵索引僅僅隻是一個叫做PRIMARY的唯一、非空的索引，且MYISAM引擎中可以不設主鍵。

3 索引的維護

B+樹為維護索引的有序，插入新值時需要做必要維護。

上圖為例，插入新行ID 700，隻需在R5的記錄後面插入。如果新插入ID 400，就麻煩了，需要邏輯上挪動後面資料，騰出位置。

更壞的結果是，如果R5所在資料頁已滿，需申請新資料頁，然後挪部分資料過去。該過程稱為頁分裂，影響性能。

頁分裂還影響資料頁的使用率。原本放在一個頁的資料，現在分兩頁，整體空間使用率降低。有分裂就有合并。當相鄰兩個頁由于删除資料，使用率很低後，會将資料頁合并。合并過程可認為是分裂過程的逆過程。

案例

建表規範：建表語句一定要有自增主鍵。

MySQL的InnoDB、MyISAM存儲引擎B+tree索引實作原理1 資料結構及算法基礎2 索引的實作3 索引的維護

到底哪些場景下應該自增主鍵？

自增主鍵一般這麼定義：

NOT NULL PRIMARY KEY AUTO_INCREMENT
  • 考慮性能

插新記錄可不指定ID，系統會擷取目前ID最大值加1作為新記錄ID，即自增主鍵符合遞增插入場景。每插入新記錄，都是追加，不涉及挪動其他記錄，也不會觸發葉節點分裂。

而有業務邏輯的字段做主鍵，不易保證有序插入，是以寫資料成本較高。

  • 考慮存儲空間

假設表中确實有個唯一字段身份證号，應該用身份證号做主鍵，還是自增字段？

因為非主鍵索引的葉節點都是主鍵值。

  • 身份證号做主鍵，每個二級索引的葉節點占約20位元組
  • 整型主鍵，隻要4位元組，長整型（bigint）8位元組

主鍵長度越小，普通索引的葉節點越小，普通索引占用空間就越小。

是以從性能和空間考慮，自增主鍵往往更合理。

有無場景适合用業務字段做主鍵？

場景如下：

  1. 隻有一個索引
  2. 該索引須是唯一索引

即KV場景。

因為沒有其他索引，是以不用考慮其他索引的葉節點大小。

要優先考慮“盡量使用主鍵查詢”原則，直接将該索引設為主鍵，避免每次查詢要搜兩棵樹。

參考

  • 《MySQL實戰》
  • 《高性能 MySQL》
存儲 sql 算法 關系型資料庫 mysql 資料庫 索引 RDS MySQL引擎表索引無效 RDS MySQL引擎表索引 算法資料存儲 資料存儲列存儲 算法與資料存儲
上一篇: ConcurrentHashMap源碼解析_05 get、remove方法
下一篇: Angular TView和LView資料結構

繼續閱讀