转载

MyISAM与InnoDB的索引结构

Mysql索引结构

Mysql非常普遍的使用在互联网公司的大大小小的业务上，而这些业务的许多性能问题都数据的查询。如果进行高质量的SQL查询，如何有效的创建索引，随用索引成为了很多复杂业务的重点关键问题。由于索引是在存储引擎层面实现的，而不是服务器层，所以索引并非标准化的，每种存储引擎的索引的工作方式都略有不同。本文将主要围绕我们最常用的MyISAM和InnoDB进行索引的介绍。

1 存储引擎：

1.1 MyISAM：

MyISAM的布局其实非常简单，它是按照插入顺序在磁盘是存储数据。如下：

MyISAM与InnoDB的索引结构

因为每一行的大小固定，索引MyISAM可以很容易从标的开始位置找到某一行的位置。其Primary Key 的结构大致如下： MyISAM与InnoDB的索引结构

而如果在其它的列上创建索引，其索引的形式与Primary Key 的结构也是相同的，可以认为Primary Key 是一个非NULL的位置索引。

1.2、InnoDB存储引擎：

InnoDB与MyISAM不同的是其支持聚集索引（后面介绍）。它存储表的结构大致如下：

聚簇索引中的每个叶子节点包含primary key的值，事务ID和回滚指针(rollback pointer)——用于事务和MVCC，和余下的列。乍看上去InnoDB和MyISAM没什么不同，但是仔细看我们应该主要到改图显示的是整个表的结构，而不只是索引。由于聚集索引索引的是整个表，所以每行不需要像MyISAM那样需要单独存储空间。聚集索引中的每一个叶子节点都包含主键值、事务ID、用于食物MVCC的会滚指针以及余下的所有列。如果主键被创建在列的前缀上，InnoDB也会包含整列及剩下的所有列。InnoDB默认的Primary Key索引即是聚集索引，既然如此，那么InnoDB的第二索引必然与主键索引不同（数据已经保存了，自然不需要另外保存一份）

通过命令查看索引：

MyISAM与InnoDB的索引结构

Non_unique ：表示数据是否唯一，0表示唯一，1表示不唯一
Key_name : 索引名称
Seq in index : 字段在索引中的顺序。例如（key name 为idx supplier provider 的索引包含两个字段：supplier id、provider_id）。索引字段的顺序非常重要。
Collation：列以什么方式存储在索引中。在MySQL中，有值‘A’（升序）或NULL（无分类）。
Cardinality：索引中唯一值的数目的估计值。通过运行ANALYZE TABLE或myisamchk -a可以更新。基数根据被存储为整数的统计数据来计数，所以即使对于小型表，该值也没有必要是精确的。基数越大，当进行联合时，MySQL使用该索引的机会就越大。平均数值组=索引基数/表总数据行，平均数值组越接近1就越有可能利用索引。
Sub_part: 如果列只是被部分地编入索引，则为被编入索引的字符的数目。如果整列被编入索引，则为NULL。
Packed : 指示关键字如何被压缩。如果没有被压缩，则为NULL。
Null : 如果列含有NULL，则含有YES。如果没有，则该列含有NO。一般来说不建议存储NULL, 这回导致索引非常难查找
Index_type：索引的方式：BTREE, FULLTEXT, HASH, RTREE
Comment ：多种评注，您可以使用db name.tbl name作为tbl name FROM db name语法的另一种形式

2 数据库索引：

Mysql的索引方式有多种，比如B－Tree索引、Hash索引、R－Tree索引等，本文主要介绍B－Tree索引、Hash索引。

2.1 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索引的时候会对存储结构进行稍作修改，例如InnoDB的B-Tree索引实际使用的存储结构是B+Tree。与B-Tree 不同的是在每一个Leaf Node上面除了存放索引键的相关信息外，还存出了指向该Leaf Node 相邻的后一个Leaf Node的指针信息，这主要是为了加快索引相邻Leaf Node 的效率考虑。

2.1.1 MyISAM上的B－Tree索引：

MyisAM索引用的B+tree来储存数据，按照插入的顺序在磁盘上存储数据：

MyISAM与InnoDB的索引结构

MyisAM索引的指针指向的是键值的地址，地址存储的是数据，并且是按照顺序存储，如下图

由于每个索引存储的都是地址信息，所以MyISAM中的Primary Key与其它的索引没有区别，Primary Key仅仅只是一个叫做PRIMARY 的唯一非空索引而已。

2.1.2 InnoDB上的B－Tree：

InnoDB的数据布局：

MyISAM与InnoDB的索引结构

下图是B－Tree索引在InnoDB和MyISAM上的结构图：

MyISAM与InnoDB的索引结构

InnoDB的数据就存储在Primary Key的索引叶子页上，而其它的索引都只是记录了索引的值和主键等其它的信息。这样在InnoDB使用主键查找一般速度会高于其它索引查找的速度。

而MyISAM索引则是想之前所过的，叶子节点上存储的是每行数据的地址，Primary Key 索引和其它索引没有本质区别。

现在我们把InnoDB的这种索引的存储数据的方式就叫做聚集索引。注意聚集索引并不是一种索引类型，而只是存储方式，具体细节依赖于聚集索引的实现。但其基本的思想就是将数据实际保存在叶子页上。"聚集"的意思是指实际的数据行和相关的键值都保存在一起，但是每个表只能有一个聚集索引，不能把一行数据保存在两个地方。

聚集索引的优点：

可以把相关数据保存在一起。例如，当查找用户信息的时候，可以按照user_id进行聚集，这样从磁盘上提取几个页面的数据就能把某个用户的邮件全部抓取出来。如果没有使用聚集，读取每个邮件都会访问磁盘。
数据访问快。聚集索引把索引和数据保存在同一棵B-Tree中，因此从聚集索引中取得数据通常比非聚集索引进行查找的要快。
使用覆盖索引的查询可以使用包含在叶子叶子节点的主键值。

聚集索引的缺点：

聚集能最大地提升I/O密集负载的性能。如果数据能装入内存，那么其顺序也就无所谓了，这样聚集就没什么用处。
插入速度严重以来与插入的顺序，按照主键的顺序插入行是吧数据装入InnoDB表的最快方法。如果没有使用按照主键顺序插入数据，那么插入之后最好使用OPTIMIZE TABLE重新组织一下。
更新索引列是昂贵的，因为它强制把每个更新行移动到新的位置。
建立在聚集索引上的表在插入新行，或者在行的主键被更新，改行必须被移动的时候会进行分页。分页放生在行的键值要求行必须呗放到一个放满数据的页的时候，此时存储引擎必须进行重新分页才能容纳下改行。分页会导致表占用更多的磁盘空间。
聚集表可能会比全表扫描慢，尤其在表存储的比较稀疏或因为分页而没有顺序存储的时候。
第二（非聚集）索引可能会比预想大，因为他们的叶子节点暴行了被引用行的主键。
第二索引访问需要两次索引查询，而非一次。

2.2 Hash索引：

Hash索引是建立在Hash表的基础上，它只对使用索引中每一列的精确查找有用。对于每一行数据，存储引擎计算出被索引列的Hash Code，计算出来的Hash Code是一个非常小的值。存储引擎将Hash Code保存在索引中，并且保存了一个指向Hash表每一行的指针。由于Hash的存储方式不同于B-Tree，所以在查找速度上Hash索引的速度是大大的优于B-Tree。但是据我们所知Hash索引很少在创建数据库索引中使用，究其原因就是在于它的索引方式所导致的一些局限性，有的时候这些局限性甚至是致命的。

Hash索引的局限性如下：

因为索引只包含了哈戏码和行指针，而不是值自身，Mysql不能使用索引的值来避免读取行。幸运的是访问内存的行很快，因此折衣板不会降低性能。
Mysql 不能使用Hash索引进行排序，因为他不会按序保存。
哈希索引不支持部分键匹配，因为他们是由呗索引的全部值计算出来的。也就是说如果在（A B）两列上有索引，WHERE语句只是用了A，那么索引就不会起作用。
哈希索引只支持使用了=、IN 和<=> 的相等比较（注意<> 和<=> 不是相同的运算符）。它们不能加快范围查询，列入Where age > 20。
访问哈希索引中的数据非常快，除非碰撞率恒高（很多值相同的Hash码）。当发生碰撞的时候，存储引擎必须访问链表中的每一个行指针，然后逐行进行数据比较，以确定正确的数据。
如果有很多碰撞，一些索引维护操作就有可能会变慢，如果在一个选择性很低（很多碰撞）的列上创建hash索引，然后从表中删除一行，那么从索引中会找到行的代价会很高。存储引擎不得不检查Hash链表中的每一行，以找到和一处被删除行的索引。

看了这些问题，是不是会发现Hash索引在建数据表的时候为什么不被提倡的原因了。

综述：

数据库的索引的目的无非就是为了提升查询的效率，但在我们往往会发现查询和修改的效率往往是相反的。MyISAM的数据是顺序存储的，所以这个优势基本上就注定了MyISAM的查询的快速，但是也恰恰由于此，其更新的时候往往要调整页的结构，所以速度比较慢。而我们经常在项目中使用的InnoDB存储则使用了聚集索引的方式，将查询与更新的速度做了平衡，这也就是为什么更多的大型项目采用InnoDB的存储方式。

原文链接： https://github.com/yushanzh/blog/issues/1

原文 http://boke.io/myisamyu-innodbde-suo-yin-jie-gou/

正文到此结束