淺析InnoDB索引結(jié)構(gòu)

0、導讀

InnoDB表的索引有哪些特性，以及索引組織結(jié)構(gòu)是怎樣的

1、InnoDB聚集索引特點

我們知道，InnoDB引擎的聚集索引組織表，必然會有一個聚集索引。

行數(shù)據(jù)（row data）存儲在聚集索引的葉子節(jié)點（除了發(fā)生overflow的列，參見 ，后面簡稱 “前置文”），并且其存儲的相對順序取決于聚集索引的順序。這里說相對順序而不是物理順序，是因為葉子節(jié)點數(shù)據(jù)頁中，行數(shù)據(jù)的物理順序和相對順序可能并不是一致的，放在后面會講。

InnoDB聚集索引的選擇先后順序是這樣的：

如果有顯式定義的主鍵（PRIMARY KEY），則會選擇該主鍵作為聚集索引

否則，選擇第一個所有列都不允許為NULL的唯一索引

若前兩者都沒有，則InnoDB會選擇內(nèi)置的DB_ROW_ID作為聚集索引，命名為GEN_CLUST_INDEX

特別提醒： DB_ROW_ID占用6個字節(jié)，每次自增，且是整個實例內(nèi)全局分配。也就是說，當前實例如果有多個表都采用了內(nèi)置的DB_ROW_ID作為聚集索引，則在這些表插入新數(shù)據(jù)時，他們的內(nèi)置DB_ROW_ID值并不是連續(xù)的，而是跳躍的。像下面這樣：

t1表的ROW_ID：1、3、7、10

t2表的ROW_ID：2、4、5、6、8、9

2、InnoDB索引結(jié)構(gòu)

InnoDB默認的索引數(shù)據(jù)結(jié)構(gòu)采用B+樹（空間索引采用R樹），索引數(shù)據(jù)存儲在葉子節(jié)點。

InnoDB的基本I/O存儲單位是數(shù)據(jù)頁(page)，一個page默認是16KB。我們在 前置文 說過，每個page默認會預(yù)留1/16空閑空間用于后續(xù)數(shù)據(jù)“變長”更新所需，因此在最理想的順序插入狀態(tài)下，其產(chǎn)生的碎片也最少，這時候差不多能填滿15/16的page空間。如果是隨機寫入的話，則page空間利用率大概是1/2 ~ 15/16。

當 row_format = DYNAMIC|COMPRESSED 時，索引最多長度為 3072字節(jié)，當 row_format = REDUNDANT|COMPACT 時，索引最大長度為 767字節(jié)。當page size不是默認的16KB時，最大索引長度限制也會跟著發(fā)生變化。

我們接下來分別驗證關(guān)于InnoDB索引的基本結(jié)構(gòu)特點。

首先創(chuàng)建如下測試表：

[root@yejr.me] [innodb]> CREATE TABLE `t1` (

? `id` int(10) unsigned NOT NULL AUTO_INCREMENT,

? `c1` int(10) unsigned NOT NULL DEFAULT '0',

? `c2` varchar(100) NOT NULL,

? `c3` varchar(100) NOT NULL,

? PRIMARY KEY (`id`),

? KEY `c1` (`c1`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

用下面的方法寫入10條測試數(shù)據(jù)：

set @uuid1=uuid(); set @uuid2=uuid();

insert into t1 select 0, round(rand()*1024),

? ? ? ? ? ? ? ? @uuid1, concat(@uuid1, @uuid2);

看下 t1 表的整體結(jié)構(gòu)：

# 用innodb_ruby工具查看

[root@yejr.me]# innodb_space -s ibdata1 -T innodb/t1 space-indexes

id? ? name? ? ? ?root? ?fseg? ? ? ? fseg_id? ?used? ? allocated? ?fill_factor

238? ?PRIMARY? ? 3? ? ? internal? ? 1? ? ? ? ?1? ? ? ?1? ? ? ? ? ?100.00%

238? ?PRIMARY? ? 3? ? ? leaf? ? ? ? 2? ? ? ? ?0? ? ? ?0? ? ? ? ? ?0.00%

239? ?c1? ? ? ? ?4? ? ? internal? ? 3? ? ? ? ?1? ? ? ?1? ? ? ? ? ?100.00%

239? ?c1? ? ? ? ?4? ? ? leaf? ? ? ? 4? ? ? ? ?0? ? ? ?0? ? ? ? ? ?0.0

?

# 用innblock工具查看

[root@yejr.me]# innblock innodb/t1.ibd scan 16

...

===INDEX_ID:238

level0 total block is (1)

block_no:? ? ?3,level:? ?0|*|

===INDEX_ID:239

level0 total block is (1)

block_no:? ? ?4,level:? ?0|*|

可以看到

3、InnoDB索引特點驗證

3.1 特點1：聚集索引葉子節(jié)點存儲整行數(shù)據(jù)

先掃描第3個page，截取其中第一條物理記錄的內(nèi)容：

[root@yejr.me]# innodb_space -s ibdata1 -T innodb/t1 -p 3 page-dump

...

records:

{:format=>:compact,

?:offset=>127,

?:header=>

? {:next=>263,

? ?:type=>:conventional,

? ?:heap_number=>2,

? ?:n_owned=>0,

? ?:min_rec=>false,

? ?:deleted=>false,

? ?:nulls=>[],

? ?:lengths=>{"c2"=>36, "c3"=>72},

? ?:externs=>[],

? ?:length=>7},

?:next=>263,

?:type=>:clustered,

?#第一條物理記錄，id=1

?:key=>[{:name=>"id", :type=>"INT UNSIGNED", :value=>1}],

?:row=>

? [{:name=>"c1", :type=>"INT UNSIGNED", :value=>777},

? ?{:name=>"c2",

? ? :type=>"VARCHAR(400)",

? ? :value=>"a1c1a7c7-bda5-11e9-8476-0050568bba82"},

? ?{:name=>"c3",

? ? :type=>"VARCHAR(400)",

? ? :value=>

? ? ?"a1c1a7c7-bda5-11e9-8476-0050568bba82a1c1aec5-bda5-11e9-8476-0050568bba82"}],

?:sys=>

? [{:name=>"DB_TRX_ID", :type=>"TRX_ID", :value=>10950},

? ?{:name=>"DB_ROLL_PTR",

? ? :type=>"ROLL_PTR",

? ? :value=>

? ? ?{:is_insert=>true,

? ? ? :rseg_id=>119,

? ? ? :undo_log=>{:page=>469, :offset=>272}}}],

?:length=>129,

?:transaction_id=>10950,

?:roll_pointer=>

? {:is_insert=>true, :rseg_id=>119, :undo_log=>{:page=>469, :offset=>272}}}

很明顯，的確是存儲了整條數(shù)據(jù)的內(nèi)容。

聚集索引樹的鍵值(key)是主鍵索引值(i=10)，聚集索引節(jié)點值(value)是其他非聚集索引列(c1,c2,c3)以及隱含列(DB_TRX_ID、DB_ROLL_PTR)。

優(yōu)化建議1：盡量不要存儲大對象數(shù)據(jù)，使得每個葉子節(jié)點都能存儲更多數(shù)據(jù)，降低碎片率，提高buffer pool利用率。此外也能盡量避免發(fā)生overflow。

3.2 特點2：聚集索引非葉子節(jié)點存儲指向子節(jié)點的指針

對上面的測試表繼續(xù)寫入新數(shù)據(jù)，直到聚集索引樹從一層分裂成兩層。

我們根據(jù)舊文 InnoDB表聚集索引層高什么時候發(fā)生變化 里的計算方式，推算出來預(yù)計一個葉子節(jié)點最多可存儲111條記錄，因此在插入第112條記錄時，就會從一層高度分裂成兩層高度。經(jīng)過實測，也的確是如此。

[root@yejr.me] [innodb]>select count(*) from t1;

+----------+

| count(*) |

+----------+

|? ? ? 112 |

+----------+

?

[root@yejr.me]# innblock innodb/t1.ibd scan 16

...

===INDEX_ID:238

level1 total block is (1)

block_no:? ? ?3,level:? ?1|*|

level0 total block is (2)

block_no:? ? ?5,level:? ?0|*|block_no:? ? ?6,level:? ?0|*|

...

此時可以看到根節(jié)點依舊是pageno=3，而葉子節(jié)點變成了[5, 6]兩個page。由此可知，根節(jié)點上應(yīng)該只有兩條物理記錄，存儲著分別指向pageno=[5, 6]這兩個page的指針。

我們解析下3號page，看看它的具體結(jié)構(gòu)：

[root@yejr.me]# innodb_space -s ibdata1 -T innodb/t1 -p 3 page-dump

...

records:

{:format=>:compact,

?:offset=>125,

?:header=>

? {:next=>138,

? ?:type=>:node_pointer,

? ?:heap_number=>2,

? ?:n_owned=>0,

? ?:min_rec=>true, #第一條記錄是min_key

? ?:deleted=>false,

? ?:nulls=>[],

? ?:lengths=>{},

? ?:externs=>[],

? ?:length=>5},

?:next=>138,

?:type=>:clustered,

?#第一條記錄，只存儲key值

?:key=>[{:name=>"id", :type=>"INT UNSIGNED", :value=>1}],

?:row=>[],

?:sys=>[],

?:child_page_number=>5, #value值是指向的葉子節(jié)點pageno=5

?:length=>8} #整條記錄消耗8字節(jié)，除去key值4字節(jié)外，指針也需要4字節(jié)

?

{:format=>:compact,

?:offset=>138,

?:header=>

? {:next=>112,

? ?:type=>:node_pointer,

? ?:heap_number=>3,

? ?:n_owned=>0,

? ?:min_rec=>false,

? ?:deleted=>false,

? ?:nulls=>[],

? ?:lengths=>{},

? ?:externs=>[],

? ?:length=>5},

?:next=>112,

?:type=>:clustered,

?#第二條記錄，只存儲key值

?:key=>[{:name=>"id", :type=>"INT UNSIGNED", :value=>56}],

?:row=>[],

?:sys=>[],

?:child_page_number=>6, #value值是指向的葉子節(jié)點pageno=6

?:length=>8}

優(yōu)化建議2: 索引列數(shù)據(jù)長度越小越好，這樣索引樹存儲效率越高，在非葉子節(jié)點能存儲越多數(shù)據(jù)，延緩索引樹層高分裂的速度，平均搜索效率更高。

3.3 特點3：輔助索引同時會存儲主鍵索引列值

在輔助索引中，總是同時會存儲主鍵索引（或者說聚集索引）的列值，其作用就是在對輔助索引掃描時，可以從葉子節(jié)點直接得到對應(yīng)的聚集索引值，并可根據(jù)該值回表查詢獲取行數(shù)據(jù)（如果需要回表查詢的話）。這個特性也被稱為Index Extensions（5.6版本之后的優(yōu)化器新特性，詳見 Use of Index Extensions）。

此外，在輔助索引的非葉子節(jié)點中，索引記錄的key值是索引定義的列值，而對應(yīng)的value值則是聚集索引列值（簡稱PKV）。如果輔助索引定義時已經(jīng)包含了部分聚集索引列，則索引記錄的value值是未被包含的余下的聚集索引列值。

創(chuàng)建如下測試表：

CREATE TABLE `t3` (

? `a` int(10) unsigned NOT NULL AUTO_INCREMENT,

? `b` int(10) unsigned NOT NULL DEFAULT '0',

? `c` varchar(20) NOT NULL DEFAULT '',

? `d` varchar(20) NOT NULL DEFAULT '',

? `e` varchar(20) NOT NULL DEFAULT '',

? PRIMARY KEY (`a`,`b`),

? KEY `k1` (`c`,`b`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

隨機插入一些測試數(shù)據(jù)：

# 調(diào)用shell腳本寫入500條數(shù)據(jù)

[root@yejr.me]# cat insert.sh

#!/bin/bash

. ~/.bash_profile

cd /data/perconad

i=1

max=500

while [ $i -le $max ]

do

?mysql -Smysql.sock -e "insert ignore into t3 select

? ? rand()*1024, rand()*1024, left(md5(uuid()),20) ,

? ? left(uuid(),20), left(uuid(),20);" innodb

?i=`expr $i + 1`

done

?

# 實際寫入498條數(shù)據(jù)（其中有2條主鍵沖突失?。?/p>

[root@yejr.me] [innodb]>select count(*) from t3;

+----------+

| count(*) |

+----------+

|? ? ? 498 |

+----------+

解析數(shù)據(jù)結(jié)構(gòu)：

# 主鍵

[root@test1 perconad]# innodb_space -s ibdata1 -T innodb/t2 space-indexes

id? ? name? ? ?root? fseg? ? ? ? fseg_id? ?used? ?allocated? ?fill_factor

245? ?PRIMARY? 3? ? ?internal? ? 1? ? ? ? ?1? ? ? 1? ? ? ? ? ?100.00%

245? ?PRIMARY? 3? ? ?leaf? ? ? ? 2? ? ? ? ?5? ? ? 5? ? ? ? ? ?100.00%

246? ?k1? ? ? ?4? ? ?internal? ? 3? ? ? ? ?1? ? ? 1? ? ? ? ? ?100.00%

246? ?k1? ? ? ?4? ? ?leaf? ? ? ? 4? ? ? ? ?2? ? ? 2? ? ? ? ? ?1

?

[root@yejr.me]# innodb_space -s ibdata1 -T innodb/t2 -p 4 page-dump

...

records:

{:format=>:compact,

?:offset=>126,

?:header=>

? {:next=>164,

? ?:type=>:node_pointer,

? ?:heap_number=>2,

? ?:n_owned=>0,

? ?:min_rec=>true,

? ?:deleted=>false,

? ?:nulls=>[],

? ?:lengths=>{"c"=>20},

? ?:externs=>[],

? ?:length=>6},

?:next=>164,

?:type=>:secondary,

?:key=>

? [{:name=>"c", :type=>"VARCHAR(80)", :value=>"00a5d42dd56632893b5f"},

? ?{:name=>"b", :type=>"INT UNSIGNED", :value=>323}],

?:row=>

? [{:name=>"a", :type=>"INT UNSIGNED", :value=>310},

? ?{:name=>"b", :type=>"INT UNSIGNED", :value=>9}],

? ?# 此處給解析成b列的值了，實際上是指向葉子節(jié)點的指針，即child_page_number=9

? ?# b列真實值是323

?:sys=>[],

?:child_page_number=>335544345,

?# 此處解析不準確，實際上是下一條記錄的record header，共6個字節(jié)

?:length=>36}

?

{:format=>:compact,

?:offset=>164,

?:header=>

? {:next=>112,

? ?:type=>:node_pointer,

? ?:heap_number=>3,

? ?:n_owned=>0,

? ?:min_rec=>false,

? ?:deleted=>false,

? ?:nulls=>[],

? ?:lengths=>{"c"=>20},

? ?:externs=>[],

? ?:length=>6},

?:next=>112,

?:type=>:secondary,

?:key=>

? [{:name=>"c", :type=>"VARCHAR(80)", :value=>"7458824a39892aa77e1a"},

? ?{:name=>"b", :type=>"INT UNSIGNED", :value=>887}],

?:row=>

? [{:name=>"a", :type=>"INT UNSIGNED", :value=>623},

? ?{:name=>"b", :type=>"INT UNSIGNED", :value=>10}],

? ?# 同上，其實是child_page_number=10，而非b列的值

?:sys=>[],

?:child_page_number=>0,

?:length=>36} #數(shù)據(jù)長度16字節(jié)

順便說下，輔助索引上沒存儲TRX_ID, ROLL_PTR這些（他們只存儲在聚集索引上）。

上面用innodb_ruby工具解析的非葉子節(jié)點部分內(nèi)容不夠準確，所以我們用二進制方式打開數(shù)據(jù)文件二次求證確認：

# 此處也可以用 hexdump 工具

[root@yejr.me]# vim -b path/t3.ibd

...

:%!xxd

?

# 找到輔助索引所在的那部分數(shù)據(jù)

0010050: 0002 0272 0000 00e1 0000 0002 01b2 0100? ...r............

0010060: 0200 1b69 6e66 696d 756d 0003 000b 0000? ...infimum......

0010070: 7375 7072 656d 756d 1410 0011 0026 3030? supremum.....&00

0010080: 6135 6434 3264 6435 3636 3332 3839 3362? a5d42dd56632893b

0010090: 3566 0000 0143 0000 0136 0000 0009 1400? 5f...C...6......

00100a0: 0019 ffcc 3734 3538 3832 3461 3339 3839? ....7458824a3989

00100b0: 3261 6137 3765 3161 0000 0377 0000 026f? 2aa77e1a...w...o

00100c0: 0000 000a 0000 0000 0000 0000 0000 0000? ................

?

# 參考page物理結(jié)構(gòu)方式進行解析，得到下面的結(jié)果

/* 第一條記錄 */

1410 0011 0026, record header, 5字節(jié)

3030 6135 6434 3264 6435 3636 3332 3839 3362 3566,c='00a5d42dd56632893b5f',20B

0000 0143, b=323, 4B

0000 0136, a=310, 4B

0000 0009, child_pageno=9, 4B

?

/* 2 */

1400 0019 ffcc, record header

3734 3538 3832 3461 3339 3839 3261 6137 3765 3161, c='7458824a39892aa77e1a'

0000 0377, b=887

0000 026f, a=623

0000 000a, child_pageno=10

現(xiàn)在反過來看，上面用innodb_ruby工具解析出來的page-dump結(jié)果應(yīng)該是這樣的才對（我只選取一條記錄，請自行對比和之前的不同之處）：

{:format=>:compact,

?:offset=>164,

?:header=>

? {:next=>112,

? ?:type=>:node_pointer,

? ?:heap_number=>3,

? ?:n_owned=>0,

? ?:min_rec=>false,

? ?:deleted=>false,

? ?:nulls=>[],

? ?:lengths=>{"c"=>20},

? ?:externs=>[],

? ?:length=>6},

?:next=>112,

?:type=>:secondary,

?:key=>

? [{:name=>"c", :type=>"VARCHAR(80)", :value=>"7458824a39892aa77e1a"},

? ?{:name=>"b", :type=>"INT UNSIGNED", :value=>887}],

?:row=> [{:name=>"a", :type=>"INT UNSIGNED", :value=>623}],

?:sys=>[],

?:child_page_number=>10,

?:length=>36}

可以看到，的確如前面所說，輔助索引的非葉子節(jié)點的value值存儲的是聚集索引列值。

優(yōu)化建議3：輔助索引列定義的長度越小越好，定義輔助索引時，沒必要顯式的加上聚集索引列（5.6版本之后）。

3.4 特點4：沒有可用的聚集索引列時，會使用內(nèi)置的ROW_ID作為聚集索引

創(chuàng)建幾個像下面這樣的表，使其選擇內(nèi)置的ROW_ID作為聚集索引：

[root@yejr.me] [innodb]> CREATE TABLE `tn1` (

? `c1` int(10) unsigned NOT NULL DEFAULT 0,

? `c2` int(10) unsigned NOT NULL DEFAULT 0

) ENGINE=InnoDB;

循環(huán)對幾個表寫數(shù)據(jù)：

insert into tt1 select 1,1;

insert into tt2 select 1,1;

insert into tt3 select 1,1;

insert into tt1 select 2,2;

insert into tt2 select 2,2;

insert into tt3 select 2,2;

查看 tn1 - tn3 表里的數(shù)據(jù)（這里由于innodb_ruby工具解析的結(jié)果不準確，所以我改用hexdump來分析）：

tn1

000c060: 0200 1a69 6e66 696d 756d 0003 000b 0000? ...infimum......

000c070: 7375 7072 656d 756d 0000 1000 2000 0000? supremum.... ...

000c080: 0003 1200 0000 003d f6aa 0000 01d9 0110? .......=........

000c090: 0000 0001 0000 0001 0000 18ff d300 0000? ................

000c0a0: 0003 1500 0000 003d f9ad 0000 01da 0110? .......=........

000c0b0: 0000 0002 0000 0002 0000 0000 0000 0000? ................

?

tn2

000c060: 0200 1a69 6e66 696d 756d 0003 000b 0000? ...infimum......

000c070: 7375 7072 656d 756d 0000 1000 2000 0000? supremum.... ...

000c080: 0003 1300 0000 003d f7ab 0000 0122 0110? .......=....."..

000c090: 0000 0001 0000 0001 0000 18ff d300 0000? ................

000c0a0: 0003 1600 0000 003d feb0 0000 01db 0110? .......=........

000c0b0: 0000 0002 0000 0002 0000 0000 0000 0000? ................

?

tn3

000c060: 0200 1a69 6e66 696d 756d 0003 000b 0000? ...infimum......

000c070: 7375 7072 656d 756d 0000 1000 2000 0000? supremum.... ...

000c080: 0003 1400 0000 003d f8ac 0000 0123 0110? .......=.....#..

000c090: 0000 0001 0000 0001 0000 18ff d300 0000? ................

000c0a0: 0003 1700 0000 003e 03b3 0000 012a 0110? .......>.....*..

000c0b0: 0000 0002 0000 0002 0000 0000 0000 0000? ................

其中表示DB_ROW_ID的值分別是：

鄭州正規(guī)不孕不育醫(yī)院：http://www.xbzztj.com/

tn1

0003 12 => (1,1)

0003 15 => (2,2)

?

tn2

0003 13 => (1,1)

0003 16 => (2,2)

?

tn3

0003 14 => (1,1)

0003 17 => (2,2)

很明顯，內(nèi)置的DB_ROW_ID的確是在整個實例級別共享自增分配的，而不是每個表獨享一個DB_ROW_ID序列。

我們可以想象下，如果一個實例中有多個表都用到這個DB_ROW_ID的話，勢必會造成并發(fā)請求的競爭/等待。此外也可能會造成主從復制環(huán)境下，從庫上relay log回放時可能會因為數(shù)據(jù)掃描機制的問題造成嚴重的復制延遲問題。詳情參考 從庫數(shù)據(jù)的查找和參數(shù)slave_rows_search_algorithms。

優(yōu)化建議4：自行顯示定義可用的聚集索引/主鍵索引，不要讓InnoDB選擇內(nèi)置的DB_ROW_ID作為聚集索引，避免潛在的性能損失。

篇幅已經(jīng)有點大了，本次的淺析工作就先到這里吧，以后再繼續(xù)。

4、幾點總結(jié)

最后針對InnoDB引擎表，總結(jié)幾條建議吧。

每個表都要有顯式主鍵，最好是自增整型，且沒有業(yè)務(wù)用途

無論是主鍵索引，還是輔助索引，都盡可能選擇數(shù)據(jù)類型較小的列

定義輔助索引時，沒必要顯式加上主鍵索引列（針對MySQL 5.6之后）

行數(shù)據(jù)越短越好，如果每個列都是固定長的則更好（不是像VARCHAR這樣的可變長度類型）

上述測試環(huán)境基于Percona Server 5.7.22：

# MySQL的版本是Percona Server 5.7.22-22，我自己下載源碼編譯的

[root@yejr.me#] mysql -Smysql.sock innodb

...

Server version: 5.7.22-22-log Source distribution

...

[root@yejr.me]> \s

...

Server version:? ? ?5.7.22-22-log Source distribution

Enjoy MySQL :)

http://www.chacha8.cn/detail/1132398242.html