MySQL索引之哈希索引和自适应哈希索引（Adaptive Hash Index）  


 官网：https://dev.mysql.com/doc/refman/5.6/en/innodb-adaptive-hash.html



索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。  


从MySQL逻辑架构来看，MySQL有三层架构，第一层连接，第二层查询解析、分析、优化、视图、缓存，第三层，存储引擎。


索引通过分开查询片，节省了扫描查找时间，大大提升查询效率。

大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。

索引主要在存储引擎层上，不同的引擎也就有不同的B-Tree算法。



0x01.Hash Index

哈希索引只有Memory, NDB两种引擎支持，Memory引擎默认支持哈希索引，如果多个hash值相同，出现哈希碰撞，那么索引以链表方式存储。

但是，Memory引擎表只对能够适合机器的内存切实有限的数据集。

要使InnoDB或MyISAM支持哈希索引，可以通过伪哈希索引来实现，叫自适应哈希索引。

主要通过增加一个字段，存储hash值，将hash值建立索引，在插入和更新的时候，建立触发器，自动添加计算后的hash到表里。

直接索引

假如有一个非常非常大的表，如下：


CREATE TABLE IF NOT EXISTS `User` (
  `id` int(10) NOT NULL COMMENT '自增id',
  `name` varchar(128) NOT NULL DEFAULT '' COMMENT '用户名',
  `email` varchar(128) NOT NULL DEFAULT '' COMMENT '用户邮箱',
  `pass` varchar(64) NOT NULL DEFAULT '' COMMENT '用户密码',
  `last` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '最后登录时间'
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

这个时候，比如说，用户登陆，我需要通过email检索出用户，通过explain得到如下：

mysql> explain SELECT id FROM User WHERE email = ‘ooxx@gmail.com’ LIMIT 1; 

+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows   | Extra       |+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+|  1 | SIMPLE      | User  | ALL  | NULL          | NULL | NULL    | NULL | 384742 | Using where |+----+-------------+-------+------+---------------+------+---------+------+--------+-------------+

 


发现 rows = 384742 也就是要在384742里面进行比对email这个字段的字符串。

这条记录运行的时间是：Query took 0.1744 seconds，数据库的大小是40万。

从上面可以说明，如果直接在email上面建立索引，除了索引区间匹配，还要进行字符串匹配比对，email短还好，如果长的话这个查询代价就比较大。

如果这个时候，在email上建立哈希索引，查询以int查询，性能就比字符串比对查询快多了。

Hash 算法

建立哈希索引，先选定哈希算法，这里选用CRC32。

《高性能MySQL》说到的方法CRC32算法，建立SHA或MD5算法是划算的，本身位数都有可能比email段长了。

INSERT UPDATE SELECT 操作

在表中添加hash值的字段：

mysql> ALTER TABLE User ADD COLUMN email_hash int unsigned NOT NULL DEFAULT 0;

接下来就是在UPDATE和INSERT的时候，自动更新 email_hash 字段，通过MySQL触发器实现：

DELIMITER |
CREATE TRIGGER user_hash_insert BEFORE INSERT ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
CREATE TRIGGER user_hash_update BEFORE UPDATE ON `User` FOR EACH ROW BEGIN
SET NEW.email_hash=crc32(NEW.email);
END;
|
DELIMITER ;



这样的话，我们的SELECT请求就会变成这样：

mysql> SELECT email, email_hash FROM User WHERE email_hash = CRC32(“F2dgTSWRBXSZ1d3O@gmail.com”) ANDemail = “F2dgTSWRBXSZ1d3O@gmail.com”;


+----------------------------+------------+
| email                      | email_hash |
+----------------------------+------------+
| F2dgTSWRBXSZ1d3O@gmail.com | 2765311122 |
+----------------------------+------------+

在没建立hash索引时候，请求时间是 0.2374 seconds，建立完索引后，请求时间直接变成 0.0003 seconds。

AND email = "F2dgTSWRBXSZ1d3O@gmail.com" 是为了防止哈希碰撞导致数据不准确。



0x02.Hash Index 缺点

哈希索引也有几个缺点：

  • 索引存放的是hash值,所以仅支持 < = > 以及 IN 操作
  • hash索引无法通过操作索引来排序，因为存放的时候经过hash计算，但是计算的hash值和存放的不一定相等，所以无法排序
  • 不能避免全表扫描，只是由于在memory表里支持非唯一值hash索引，就是不同的索引键，可能存在相同的hash值
  • 如果哈希碰撞很多的话，性能也会变得很差
  • 哈希索引无法被用来避免数据的排序操作



 警惕 InnoDB 和 MyISAM 创建 Hash 索引陷阱  

MySql 最常用存储引擎 InnoDB 和 MyISAM 都不支持 Hash 索引，它们默认的索引都是 B-Tree。但是如果你在创建索引的时候定义其类型为 Hash，MySql 并不会报错，而且你通过 SHOW CREATE TABLE 查看该索引也是 Hash，只不过该索引实际上还是 B-Tree。  
比如表 data_dict 的 DDL：  

[sql]           view plain      copy        print     ?

  1. CREATE TABLE `data_dict` (  
  2.   `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',  
  3.   `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',  
  4.   `data_name` varchar(64) NOT NULL COMMENT '数据字典值',  
  5.   PRIMARY KEY (`data_type`,`data_code`)  
  6. ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='数据字典表';  


我们为 data_name 字段建立 Hash 索引：  

[sql]           view plain      copy        print     ?

  1. ALTER TABLE data_dict ADD INDEX data_dict_dn USING HASH (data_name);  


打印结果：  
受影响的行: 0
时间: 0.345s  
然后查看建表 DDL：  

[sql]           view plain      copy        print     ?

  1. SHOW CREATE TABLE data_dict;  


打印结果：  
CREATE TABLE `data_dict` (
  `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',
  `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',
  `data_name` varchar(64) NOT NULL COMMENT '数据字典值',
  PRIMARY KEY (`data_type`,`data_code`),
  KEY `data_dict_dn` (`data_name`) USING HASH
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='数据字典表'  
是 Hash，所以我们以为创建 Hash 索引成功。  
事实上并非如此，我们都被 MySql 给骗了，我们使用 SHOW INDEXES FROM 语句对该表索引进行检索：  

[sql]           view plain      copy        print     ?

  1. SHOW INDEXES FROM data_dict;  


打印结果：  

打回原形了。不过也不要失望，虽然常见存储引擎并不支持 Hash 索引，但 InnoDB 有另一种实现方法：自适应哈希索引。InnoDB 存储引擎会监控对表上索引的查找，如果观察到建立哈希索引可以带来速度的提升，则建立哈希索引。  
我们可以通过 SHOW ENGINE INNODB STATUS 来查看当前自适应哈希索引的使用状况：  
=====================================
2015-07-07 10:51:19 1d68 INNODB MONITOR OUTPUT
=====================================
Per second averages calculated from the last 36 seconds
......
-------------------------------------
INSERT BUFFER AND ADAPTIVE HASH INDEX
-------------------------------------
Ibuf: size 1, free list len 2633, seg size 2635, 0 merges
merged operations:
 insert 0, delete mark 0, delete 0
discarded operations:
 insert 0, delete mark 0, delete 0
Hash table size 348731, node heap has 2 buffer(s)
0.00 hash searches/s, 0.00 non-hash searches/s
......  
从中我们可以看到自适应哈希索引的相关信息：有使用大小、使用情况、每秒使用自适应哈希索引搜索的情况等。  
MySql 各种存储引擎的特性对比详单：  

从中我们可以看出，  

  • InnoDB 支持事务，支持行级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
  • MyISAM 不支持事务，支持表级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
  • Memory 不支持事务，支持表级别锁定，支持 B-tree、Hash 等索引，不支持 Full-text 索引；
  • NDB 支持事务，支持行级别锁定，支持 Hash 索引，不支持 B-tree、Full-text 等索引；
  • Archive 不支持事务，支持表级别锁定，不支持 B-tree、Hash、Full-text 等索引；

可以使用 SHOW ENGINES 语句查看你的 MySql Server 所支持的存储引擎，比如笔者用于本机测试的 5.6.25-log Win 版的查看结果如下：  

从中可以看出，InnoDB 是该版本 MySql 的默认存储引擎，也只有 InnoDB 能够支持事务、行级别锁定、外键；支持的 MEMORY 是基于哈希的，数据都存放于内存，适用于临时表。没有看到既支持事务又支持哈希索引的 NDB 的身影。

为印证默认的存储引擎，我们创建一个测试表 data_dict_test，注意建表语句里没有定义存储引擎：


[sql]           view plain      copy        print     ?

  1. CREATE TABLE `data_dict_test` (  
  2.   `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',  
  3.   `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',  
  4.   `data_name` varchar(64) NOT NULL COMMENT '数据字典值',  
  5.   PRIMARY KEY (`data_type`,`data_code`)  
  6. ) DEFAULT CHARSET=utf8 COMMENT='数据字典表';  

打印结果：  


[SQL] CREATE TABLE `data_dict_test` (
  `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',
  `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',
  `data_name` varchar(64) NOT NULL COMMENT '数据字典值',
  PRIMARY KEY (`data_type`,`data_code`)
) DEFAULT CHARSET=utf8 COMMENT='数据字典表';
受影响的行: 0
时间: 0.262s

然后查看建表 DDL：


[sql]           view plain      copy        print     ?

  1. SHOW CREATE TABLE data_dict_test;  

打印结果：  


CREATE TABLE `data_dict_test` (
  `data_type` varchar(32) NOT NULL COMMENT '数据字典类型',
  `data_code` tinyint(4) NOT NULL COMMENT '数据字典代码',
  `data_name` varchar(64) NOT NULL COMMENT '数据字典值',
  PRIMARY KEY (`data_type`,`data_code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='数据字典表'

这次 SHOW CREATE TABLE 没有欺骗我们，明确给出的就是 InnoDB，虽然我们建表时没有指定。

笔者建议使用 SHOW TABLE STATUS 语句来查看特定表的存储引擎：


[sql]           view plain      copy        print     ?

  1. SHOW TABLE STATUS WHERE NAME = 'data_dict_test';  

打印结果：  



参考资料

  • http://dev.mysql.com/doc/refman/5.6/en/storage-engines.html
  • http://dba.stackexchange.com/questions/2817/why-does-mysql-not-have-hash-indices-on-myisam-or-innodb

btree索引：

如果没有特别指明类型，多半说的就是btree索引，它使用btree数据结构来存储数据，大多数mysql引擎都支持这种索引，archive引擎是一个例外，5.1之前这个引擎不支持任何索引，5.1开始才支持单列自增的索引。innodb使用b+tree=btree（btree已经不使用了）

存储引擎以不同的方式使用btree索引，性能也各不相同，各有优劣，如:myisam使用前缀压缩技术使得索引更小（但也可能导致连接表查询性能降低），但innodb则按照原数据格式进行存储，再如：myisam索引通过数据的物理位置来引用被索引的行，而innodb则根据主键来引用被索引的行。

btree通常意味着所有的值都是按照顺序存储的，并且每一个叶子页到根的距离相同

，下图是innodb索引工作示意图，myisam使用的结构有所不同，但基本思想类似：

                                                                  图片来源于高性能mysql第三版

btree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索，根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找,通过比较节点页的值和要查找的值可以找到合适的指针进入下一层子节点，这些指针实际上定义了子节点页中值的上限和下限，最终存储引擎要么是找到对应的值，要么是该记录不存在。

叶子节点比较特别，他们的指针指向的是被索引的数据，而不是其他的节点页（不同的引擎指针类型不同），其实在根节点与叶子节点之间可能有很多层节点页，树的深度和表的大小直接相关。

 

btree树索引列是顺序组织存储的，所以很适合查找范围数据，如

有表：

create table people(last_name varchar(50) not null,first_name varchar(50) not null,dob date not null,gender enum(‘m’,’f’) not null,key(last_name,first_name,dob));

 

对于表中的每一行数据，索引中包含了last_name,first_name,dob列的值，下图显示了该索引是如何组织数据的存储的：

                                                         图片来源于高性能mysql第三版

注意：索引对多个值进行排序的依据是create table语句中定义索引时的列顺序，上图中，最后两个值的姓名都一样时，就按照出生日期来排序了。

 

可以使用btree索引的查询类型，btree索引使用用于全键值、键值范围、或者键前缀查找，其中键前缀查找只适合用于根据最左前缀的查找。前面示例中创建的多列索引对如下类型的查询有效：

A：全值匹配

全值匹配指的是和索引中的所有列进行匹配，即可用于查找姓名和出生日期

B：匹配最左前缀

如：只查找姓，即只使用索引的第一列

C：匹配列前缀

也可以只匹配某一列值的开头部分，如：匹配以J开头的姓的人，这里也只是使用了索引的第一列，且是第一列的一部分

D：匹配范围值

如查找姓在allen和barrymore之间的人，这里也只使用了索引的第一列

E：精确匹配某一列并范围匹配另外一列

如查找所有姓为allen，并且名字字母是K开头的，即，第一列last_name精确匹配，第二列first_name范围匹配

F：只访问索引的查询

btree通常可以支持只访问索引的查询，即查询只需要访问索引，而无需访问数据行，即，这个就是覆盖索引的概念。需要访问的数据直接从索引中取得。

 

因为索引树中的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的order by操作，一般来说，如果btree可以按照某种方式查找的值，那么也可以按照这种方式用于排序，所以，如果order by子句满足前面列出的几种查询类型，则这个索引也可以满足对应的排序需求。

 

下面是关于btree索引的限制：

A：如果不是按照索引的最左列开始查找的，则无法使用索引(注意，这里不是指的where条件的顺序，即where条件中，不管条件顺序，只要where中出现的列在多列索引中能够从最左开始连贯起来就能使用到多列索引)

B：不能跳过索引中的列，如：查询条件为姓和出生日期，跳过了名字列，这样，多列索引就只能使用到姓这一列

C：如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查询，如：where last_name=xxx and first_name like ‘xxx%’ and dob=’xxx’;这样，first_name列可以使用索引，这列之后的dob列无法使用索引。

 

哈希索引：

基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列的值计算一个哈希码，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码不一样，哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

 

在mysql中，只有memory引擎显式支持哈希索引，这也是memory引擎表的默认索引类型，memory也支持btree，值得一提的是，memory引擎是支持非唯一哈希索引的。在数据库世界里是比较与众不同，如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

示例：

mysql> create table testhash(fname varchar(50) not null,lname varchar(50) not null,key using hash(fname)) engine=memory;

Query OK, 0 rows affected (0.01 sec)

 

mysql> insert into testhash values('Arjen','Lentz'),('Baron','Schwartz'),('Peter','Zaitsev'),('Vadim','Tkachenko');

Query OK, 4 rows affected (0.00 sec)

Records: 4  Duplicates: 0  Warnings: 0

 

mysql> select * from testhash;

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

| fname | lname     |

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

| Arjen | Lentz     |

| Baron | Schwartz  |

| Peter | Zaitsev   |

| Vadim | Tkachenko |

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

4 rows in set (0.00 sec)

 

假设索引使用假想的哈希函数f(),它返回下面的值：

f('Arjen')=2323

f('Baron')=7437

f('Peter')=8784

f('Vadim')=2458

 

则哈希索引的数据结构如下：

槽：        值：

2323        指向第1行的指针

2458        指向第4行的指针

7437        指向第2行的指针

8784        指向第3行的指针

  

每个槽的编号是顺序的，但是数据行不是顺序的。下面来看一句查询：

select lname from testhash where fname='Peter';

  

mysql先计算Peter的哈希值，并使用该值寻找对应的记录指针，因为f(‘Peter’)=8784，所以mysql在索引中查找8784，可以找到指向第三行的指针，最后一步是比较第三行的值是否为Peter，以确保就是要查找的行。因为索引自身只需要存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快，然而，哈希索引也有限制，如下：

 

A：哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行（即不能使用哈希索引来做覆盖索引扫描），不过，访问内存中的行的速度很快（因为memory引擎的数据都保存在内存里），所以大部分情况下这一点对性能的影响并不明显。

B：哈希索引数据并不是按照索引列的值顺序存储的，所以也就无法用于排序

C：哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引的全部列值内容来计算哈希值的。如：数据列（a,b）上建立哈希索引，如果只查询数据列a，则无法使用该索引。

D：哈希索引只支持等值比较查询，如：=,in(),<=>(注意，<>和<=>是不同的操作)，不支持任何范围查询（必须给定具体的where条件值来计算hash值，所以不支持范围查询）。

E：访问哈希索引的数据非常快，除非有很多哈希冲突，当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。

F：如果哈希冲突很多的话，一些索引维护操作的代价也很高，如：如果在某个选择性很低的列上建立哈希索引（即很多重复值的列），那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。

 

从上面描述可知，哈希索引只适合某些特定的场景，而一旦适合哈希索引，则它带来的性能提升非常明显，除了memory引擎外，NDB引擎也支持唯一哈希索引，且NDB存储引擎中作用非常特殊，但这里不讨论。

 

innodb引擎有一个特殊的功能叫做自适应哈希索引，当innodb注意到某些索引值被使用的非常频繁时，它会在内存中基于btree索引之上再创建一个哈希索引，这样就让btree索引也具有哈希索引的一些优点，比如：快速的哈希查找，这是一个全自动的，内部的行为，用户无法控制或者配置，不过如果有必要，可以选择关闭这个功能（innodb_adaptive_hash_index=OFF，默认为ON）。

 

MySQL中自适应哈希索引  

自适应哈希索引采用之前讨论的哈希表的方式实现，不同的是，这仅是数据库自身创建并使用的，DBA本身并不能对其进行干预。自适应哈希索引近哈希函数映射到一个哈希表中，因此对于字典类型的查找非常快速，如SELECT * FROM TABLE WHERE index_col='xxx'但是对于范围查找就无能为力。通过SHOW ENGINE INNODB STATUS 可以看到当前自适应哈希索引的使用情况

-------------------------------------    
INSERT BUFFER AND ADAPTIVE HASH INDEX    
-------------------------------------    
Ibuf: size 1, free list len 0, seg size 2, 94 merges    
merged operations:    
 insert 280, delete mark 0, delete 0    
discarded operations:    
 insert 0, delete mark 0, delete 0    
Hash table size 4425293, node heap has 1337 buffer(s)    
174.24 hash searches/s, 169.49 non-hash searches/s        

现在可以看到自适应哈希索引的使用信息了。包括自适应哈希索引的大小、使用情况，每秒使用自适应哈希索引搜索的情况。需要注意的是，哈希索引只能用来搜索等值的查询，如 

SELECT * FROM table WHERE index_col='xxx'

 

而对于其他查找类型，如范围查找，是不能使用哈希索引的。因此这里出现no--hash searches的情况，通过hash searches:non-hash searches可以大概了解使用哈希索引后的效率

由于自适应哈希索引是由InnoDB存储引擎自己控制的，因此这里的这些信息只仅供参考。不过可以通过参数innodb_adaptive_hash_index来禁用或启动此特性，默认是开启

 

Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。  

可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。

（1）Hash 索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。

（2）Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；

（3）Hash 索引不能利用部分索引键查询。

对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。

（4）Hash 索引在任何时候都不能避免表扫描。

前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

（5）Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下



2. B-Tree索引 

      B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型，除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此，实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型，这主要是因为 B-Tree 索引的存储结构在数据库的数据检 索中有非常优异的表现。 
      一般来说， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的，也就是所有实际需要的数据都存放于 Tree 的 Leaf Node ，而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的，所以我们大家都称之为 B-Tree 索引当然，可能各种数据库（或 MySQL 的各种存储引擎）在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree ，也就是在 B-Tree 数据结构的基础上做了很小的改造，在每一个 
Leaf Node 上面出了存放索引键的相关信息之外，还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息，这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。 
      在 Innodb 存储引擎中，存在两种不同形式的索引，一种是 Cluster 形式的主键索引（ Primary Key ），另外一种则是和其他存储引擎（如 MyISAM 存储引擎）存放形式基本相同的普通 B-Tree 索引，这种索引在 Innodb 存储引擎中被称为 Secondary Index 。下面我们通过图示来针对这两种索引的存放 
形式做一个比较。 

     

      图示中左边为 Clustered 形式存放的 Primary Key ，右侧则为普通的 B-Tree 索引。两种 Root Node 和 Branch Nodes 方面都还是完全一样的。而 Leaf Nodes 就出现差异了。在 Prim中， Leaf Nodes 存放的是表的实际数据，不仅仅包括主键字段的数据，还包括其他字段的数据据以主键值有序的排列。而 Secondary Index 则和其他普通的 B-Tree 索引没有太大的差异，Leaf Nodes 出了存放索引键 的相关信息外，还存放了 Innodb 的主键值。 

      所以，在 Innodb 中如果通过主键来访问数据效率是非常高的，而如果是通过 Secondary Index 来访问数据的话， Innodb 首先通过 Secondary Index 的相关信息，通过相应的索引键检索到 Leaf Node之后，需要再通过 Leaf Node 中存放的主键值再通过主键索引来获取相应的数据行。MyISAM 存储引擎的主键索引和非主键索引差别很小，只不过是主键索引的索引键是一个唯一且非空 的键而已。而且 MyISAM 存储引擎的索引和 Innodb 的 Secondary Index 的存储结构也基本相同，主要的区别只是 MyISAM 存储引擎在 Leaf Nodes 上面出了存放索引键信息之外，再存放能直接定位到 MyISAM 数据文件中相应的数据行的信息（如 Row Number ），但并不会存放主键的键值信息  

 






About Me

.............................................................................................................................................

● 本文作者：小麦苗，部分内容整理自网络，若有侵权请联系小麦苗删除

● 本文在itpub（http://blog.itpub.net/26736162/abstract/1/）、博客园（http://www.cnblogs.com/lhrbest）和个人微信公众号（xiaomaimiaolhr）上有同步更新

● 本文itpub地址：http://blog.itpub.net/26736162/abstract/1/

● 本文博客园地址：http://www.cnblogs.com/lhrbest

● 本文pdf版、个人简介及小麦苗云盘地址：http://blog.itpub.net/26736162/viewspace-1624453/

● 数据库笔试面试题库及解答：http://blog.itpub.net/26736162/viewspace-2134706/

● DBA宝典今日头条号地址：http://www.toutiao.com/c/user/6401772890/#mid=1564638659405826

.............................................................................................................................................

● QQ群号：230161599（满）、618766405

● 微信群：可加我微信，我拉大家进群，非诚勿扰

● 联系我请加QQ好友（646634621），注明添加缘由

● 于 2017-09-01 09:00 ~ 2017-09-30 22:00 在魔都完成

● 文章内容来源于小麦苗的学习笔记，部分整理自网络，若有侵权或不当之处还请谅解

● 版权所有，欢迎分享本文，转载请保留出处

.............................................................................................................................................

● 小麦苗的微店：https://weidian.com/s/793741433?wfr=c&ifr=shopdetail

● 小麦苗出版的数据库类丛书：http://blog.itpub.net/26736162/viewspace-2142121/

.............................................................................................................................................

使用微信客户端扫描下面的二维码来关注小麦苗的微信公众号（xiaomaimiaolhr）及QQ群（DBA宝典），学习最实用的数据库技术。

   小麦苗的微信公众号      小麦苗的DBA宝典QQ群1     小麦苗的DBA宝典QQ群2        小麦苗的微店

.............................................................................................................................................







来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/26736162/viewspace-2144680/，如需转载，请注明出处，否则将追究法律责任。

©著作权归作者所有：来自51CTO博客作者小麦苗DB宝的原创作品，如需转载，请注明出处，否则将追究法律责任

更多相关文章

  1. 超极本盘符丢失找到数据的办法
  2. MySQL默认数据库介绍
  3. Oracle BLOB类型的数据如何查看和下载？
  4. Oracle DB 18c - 手动升级到 18c 的完整核对清单 (文档 ID 2469
  5. 事务的4种隔离级别（Isolation Level）分别是什么？
  6. MySQL 续集 02
  7. MySQL 续集 03
  8. MySQL 续集 04
  9. Oracle分区表之分区范围扫描（PARTITION RANGE ITERATOR）与位图范围

随机推荐

  1. Android UI之TextView实现跑马灯效果
  2. 第16天android：看android的书籍
  3. FAQ_15_android Imageview ImageButton B
  4. [Android] ExpandableListView 子目录点
  5. android shape用法
  6. Android内存管理机制
  7. Android 4.0.3 CTS 测试
  8. android系统工具之 draw9patch超详细教程
  9. Spinner的三级联动
  10. ExpandableListView 怎么和其他组件相互