浅析InnoDB索引结构

0、导读

InnoDB表的索引有哪些特性，以及索引组织结构是怎样的

1、InnoDB聚集索引特点

我们知道，InnoDB引擎的聚集索引组织表，必然会有一个聚集索引。

行数据（row data）存储在聚集索引的叶子节点（除了发生overflow的列，参见 ，后面简称 “前置文”），并且其存储的相对顺序取决于聚集索引的顺序。这里说相对顺序而不是物理顺序，是因为叶子节点数据页中，行数据的物理顺序和相对顺序可能并不是一致的，放在后面会讲。

InnoDB聚集索引的选择先后顺序是这样的：

如果有显式定义的主键（PRIMARY KEY），则会选择该主键作为聚集索引

否则，选择第一个所有列都不允许为NULL的唯一索引

若前两者都没有，则InnoDB会选择内置的DB_ROW_ID作为聚集索引，命名为GEN_CLUST_INDEX

特别提醒： DB_ROW_ID占用6个字节，每次自增，且是整个实例内全局分配。也就是说，当前实例如果有多个表都采用了内置的DB_ROW_ID作为聚集索引，则在这些表插入新数据时，他们的内置DB_ROW_ID值并不是连续的，而是跳跃的。像下面这样：

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

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

2、InnoDB索引结构

InnoDB默认的索引数据结构采用B+树（空间索引采用R树），索引数据存储在叶子节点。

InnoDB的基本I/O存储单位是数据页(page)，一个page默认是16KB。我们在 前置文 说过，每个page默认会预留1/16空闲空间用于后续数据“变长”更新所需，因此在最理想的顺序插入状态下，其产生的碎片也最少，这时候差不多能填满15/16的page空间。如果是随机写入的话，则page空间利用率大概是1/2 ~ 15/16。

当 row_format = DYNAMIC|COMPRESSED 时，索引最多长度为 3072字节，当 row_format = REDUNDANT|COMPACT 时，索引最大长度为 767字节。当page size不是默认的16KB时，最大索引长度限制也会跟着发生变化。

我们接下来分别验证关于InnoDB索引的基本结构特点。

首先创建如下测试表：

[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条测试数据：

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

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

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

看下 t1 表的整体结构：

# 用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：聚集索引叶子节点存储整行数据

先扫描第3个page，截取其中第一条物理记录的内容：

[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}}}

很明显，的确是存储了整条数据的内容。

聚集索引树的键值(key)是主键索引值(i=10)，聚集索引节点值(value)是其他非聚集索引列(c1,c2,c3)以及隐含列(DB_TRX_ID、DB_ROLL_PTR)。

优化建议1：尽量不要存储大对象数据，使得每个叶子节点都能存储更多数据，降低碎片率，提高buffer pool利用率。此外也能尽量避免发生overflow。

3.2 特点2：聚集索引非叶子节点存储指向子节点的指针

对上面的测试表继续写入新数据，直到聚集索引树从一层分裂成两层。

我们根据旧文 InnoDB表聚集索引层高什么时候发生变化 里的计算方式，推算出来预计一个叶子节点最多可存储111条记录，因此在插入第112条记录时，就会从一层高度分裂成两层高度。经过实测，也的确是如此。

[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|*|

...

此时可以看到根节点依旧是pageno=3，而叶子节点变成了[5, 6]两个page。由此可知，根节点上应该只有两条物理记录，存储着分别指向pageno=[5, 6]这两个page的指针。

我们解析下3号page，看看它的具体结构：

[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值是指向的叶子节点pageno=5

 :length=>8} #整条记录消耗8字节，除去key值4字节外，指针也需要4字节

{: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值是指向的叶子节点pageno=6

 :length=>8}

优化建议2: 索引列数据长度越小越好，这样索引树存储效率越高，在非叶子节点能存储越多数据，延缓索引树层高分裂的速度，平均搜索效率更高。

3.3 特点3：辅助索引同时会存储主键索引列值

在辅助索引中，总是同时会存储主键索引（或者说聚集索引）的列值，其作用就是在对辅助索引扫描时，可以从叶子节点直接得到对应的聚集索引值，并可根据该值回表查询获取行数据（如果需要回表查询的话）。这个特性也被称为Index Extensions（5.6版本之后的优化器新特性，详见 Use of Index Extensions）。

此外，在辅助索引的非叶子节点中，索引记录的key值是索引定义的列值，而对应的value值则是聚集索引列值（简称PKV）。如果辅助索引定义时已经包含了部分聚集索引列，则索引记录的value值是未被包含的余下的聚集索引列值。

创建如下测试表：

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;

随机插入一些测试数据：

# 调用shell脚本写入500条数据

[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条数据（其中有2条主键冲突失败）

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

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

| count(*) |

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

|      498 |

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

解析数据结构：

# 主键

[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列的值了，实际上是指向叶子节点的指针，即child_page_number=9

   # b列真实值是323

 :sys=>[],

 :child_page_number=>335544345,

 # 此处解析不准确，实际上是下一条记录的record header，共6个字节

 :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} #数据长度16字节

顺便说下，辅助索引上没存储TRX_ID, ROLL_PTR这些（他们只存储在聚集索引上）。

上面用innodb_ruby工具解析的非叶子节点部分内容不够准确，所以我们用二进制方式打开数据文件二次求证确认：

# 此处也可以用 hexdump 工具

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

...

:%!xxd

# 找到辅助索引所在的那部分数据

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物理结构方式进行解析，得到下面的结果

/* 第一条记录 */

1410 0011 0026, record header, 5字节

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

现在反过来看，上面用innodb_ruby工具解析出来的page-dump结果应该是这样的才对（我只选取一条记录，请自行对比和之前的不同之处）：

{: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}

可以看到，的确如前面所说，辅助索引的非叶子节点的value值存储的是聚集索引列值。

优化建议3：辅助索引列定义的长度越小越好，定义辅助索引时，没必要显式的加上聚集索引列（5.6版本之后）。

3.4 特点4：没有可用的聚集索引列时，会使用内置的ROW_ID作为聚集索引

创建几个像下面这样的表，使其选择内置的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;

循环对几个表写数据：

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 表里的数据（这里由于innodb_ruby工具解析的结果不准确，所以我改用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的值分别是：

郑州正规不孕不育医院：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)

很明显，内置的DB_ROW_ID的确是在整个实例级别共享自增分配的，而不是每个表独享一个DB_ROW_ID序列。

我们可以想象下，如果一个实例中有多个表都用到这个DB_ROW_ID的话，势必会造成并发请求的竞争/等待。此外也可能会造成主从复制环境下，从库上relay log回放时可能会因为数据扫描机制的问题造成严重的复制延迟问题。详情参考 从库数据的查找和参数slave_rows_search_algorithms。

优化建议4：自行显示定义可用的聚集索引/主键索引，不要让InnoDB选择内置的DB_ROW_ID作为聚集索引，避免潜在的性能损失。

篇幅已经有点大了，本次的浅析工作就先到这里吧，以后再继续。

4、几点总结

最后针对InnoDB引擎表，总结几条建议吧。

每个表都要有显式主键，最好是自增整型，且没有业务用途

无论是主键索引，还是辅助索引，都尽可能选择数据类型较小的列

定义辅助索引时，没必要显式加上主键索引列（针对MySQL 5.6之后）

行数据越短越好，如果每个列都是固定长的则更好（不是像VARCHAR这样的可变长度类型）

上述测试环境基于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