MySQL源码：索引相关的数据结构(前篇)

很枯燥的，配首背景音乐吧：

本文将尝试介绍MySQL索引存储相关的数据结构。程序=数据结构+算法，了解数据结构，然后就可以进一步了解MySQL源码中如何使用索引，如何选择自己的执行计划。

1. MySQL如何描述某个数据表的索引

MySQL使用TABLE对象来描述一个数据表，那么数据表的索引是如何描述，索引的统计信息又是如何存储的呢? 例如我们有如下数据表：

CREATE TABLE `users` (
  `id` int(11) NOT NULL,
  `nick` varchar(32) DEFAULT NULL,
  `reg_date` datetime DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `IND_NICK` (`nick`),
  KEY `IND_REGDATE` (`reg_date`)
)

该表有索引，PRIMARY KEY、IND_NICK、IND_REGDATE，我们来看看MySQL内部是如何存储这三个索引，以及如何使用这些索引的统计信息的。下图，描述了存储一个数据表索引的主要结构：

MySQL使用TABLE对象描述一个数据表，他的成员key_info（类型为KEY）描述这个表的全部索引

key_info是一个数组，每一个元素是一个KEY(vim -t KEY查看)对象，代表了一个索引，顺序的，整个数组代表了这个表的全部索引

key_info（KEY对象）的成员key_part，是指向KEY_PART_INFO数组的指针，该数组描述了某个索引所有的索引列信息，数组的每个元素代表了一个索引列

最后，key_part的成员field指向该索引列对应的数据表字段

2. GDB打印观察索引信息

2.1 打印索引基本信息

某个索引（例如IND_NICK）的基本信息是存储在KEY结构(table->key_info数组)中，这里，我们来打印索引IND_NICK的基本信息来观察KEY结构：

(gdb) p s->table->key_info[1]
$26 = {
  key_length = 67, 
  flags = 104, 
  key_parts = 1, 
  extra_length = 3, 
  usable_key_parts = 1, 
  block_size = 1024, 
  algorithm = HA_KEY_ALG_UNDEF, 
  {
    parser = 0x0, 
    parser_name = 0x0
  }, 
  key_part = 0x7f6514020860, 
  name = 0x7f651401fc11 "IND_NICK", 
  rec_per_key = 0x7f651401fa68, 
  handler = {
    bdb_return_if_eq = 0
  }, 
  table = 0x7f6514023d30
}

key_length = 67：表示这个索引入口长为67(不包括rowid),32*2 + 1(NULL) + VARCHAR变成信息

flags = 104 这是一个索引信息的标志位，存储了这个索引的一些重要属性，例如是不是唯一索引，索引中有没有变长字段，是不是一个全文索引等，104表示为二进制，即是1101000，也等于8+32+64，也就是HA_VAR_LENGTH_KEY|HA_BINARY_PACK_KEY|HA_NULL_PART_KEY

更多flags类型：

#define HA_NOSAME                1      /* Set if not dupplicated records */
#define HA_PACK_KEY              2      /* Pack string key to previous key */
#define HA_SPACE_PACK_USED       4      /* Test for if SPACE_PACK used */
#define HA_VAR_LENGTH_KEY        8
#define HA_AUTO_KEY              16
#define HA_BINARY_PACK_KEY       32     /* Packing of all keys to prev key */
#define HA_NULL_PART_KEY         64
#define HA_FULLTEXT             128     /* For full-text search */
#define HA_UNIQUE_CHECK         256     /* Check the key for uniqueness */
#define HA_SPATIAL              1024    /* For spatial search */
#define HA_NULL_ARE_EQUAL       2048    /* NULL in key are cmp as equal */
#define HA_GENERATED_KEY        8192    /* Automaticly generated key */

key_part = 0x7f6514020860 这个指针指向一个KEY_PART_INFO数组，存储了索引各个列的信息。

2.2 打印索引某一列的基本信息

(gdb) p s->table->key_info[1]->key_part[0]
$29 = {
  field = 0x7f6514020588, 
  offset = 5, 
  null_offset = 0, 
  length = 64, 
  store_length = 67, 
  key_type = 32768, 
  fieldnr = 2, 
  key_part_flag = 24, 
  type = 15 '\017', 
  null_bit = 1 '\001'
}

field = 0x7f6514020588 指向这个索引列使用数据表的那一列

offset = 5 改索引列从索引串的第一个偏移开始

null_offset = 0 null信息存储偏移

length = 64, 索引串长度

store_length = 67, 整个索引入口长度

…

2.3 打印索引某列详情

(gdb) p *s->table->key_info[1]->key_part[0]->field
$36 = {
  ...
  table = 0x7f6514023d30, 
  ...
  field_name = 0x7f651401fcf4 "nick", 
  ...
  key_start = {
    map = 2
  }, 
  part_of_key = {
    map = 2
  }, 
  part_of_key_not_clustered = {
    map = 2
  }, 
  part_of_sortkey = {
    map = 2
  }, 
  ...
}

table = 0x7f6514023d30 指向该列所在的数据表

field_name = 0x7f651401fcf4 “nick” 列名

key_start = 2 包含这个字段且为索引第一个字段的索引编号，2的二进制是10，也就是第二索引以该字段为起始

3. MySQL源码中如何使用索引信息

下面摘抄函数store_create_info(显示SHOW CREATE TABLE命令)显示索引信息部分的代码如下：

1351   for (uint i=0 ; i < share->keys ; i++,key_info++)
1352   {
1353     KEY_PART_INFO *key_part= key_info->key_part;
...
1357     if (i == primary_key && !strcmp(key_info->name, primary_key_name))
1358     {
1359       found_primary=1;
1364       packet->append(STRING_WITH_LEN("PRIMARY KEY"));
1365     }
1366     else if (key_info->flags & HA_NOSAME)
1367       packet->append(STRING_WITH_LEN("UNIQUE KEY "));
...
1372     else
1373       packet->append(STRING_WITH_LEN("KEY "));
...
1380     for (uint j=0 ; j < key_info->key_parts ; j++,key_part++)
1381     {
...
1401     }
1402     packet->append(')');
1403     store_key_options(thd, packet, table, key_info);
1404     if (key_info->parser)
1405     {
...
1410     }
1411   }

小结：

(1) 可以看到MySQL如何遍历一个表的所有索引

key_info= table->key_info;
for (uint i=0 ; i < share->keys ; i++,key_info++)
{
  ...
}

(2) 可以看到MySQL如何根据key_info->flags字段如何区分唯一索引，全文索引等

(3) 可以看到MySQL如何遍历一个索引的所有字段：

KEY_PART_INFO *key_part= key_info->key_part;
for (uint j=0 ; j < key_info->key_parts ; j++,key_part++)
{
  ...
}

(4) 查看完整的这个函数还可以看到MySQL如何读取数据表的各个column

[全文完]

orczhou.com