MySQL中MyISAM和InnoDB对B-Tree索引不同的实现方式

索引是 MySQL数据库很重要的一部分,它对数据表查询性能的好坏起着决定性的作用,对大表尤甚。 
作为索引中最为常见的一种类型,B-Tree索引大都采用的是 B+Tree数据结构来存储数据(NDB集群存储引擎内部实际上采用 T-Tree结构存储这种索引)。B-Tree通常也意味着所有的值都是按顺序存储的。 
大多数的 MySQL引擎都支持这种索引,而不同的存储引擎以不同的方式来实现 B-Tree索引,性能方面各有优劣。 
下面分别讲述 MyISAM 和 InnoDB 的B-Tree索引实现方式。

MyISAM索引的实现

MyISAM索引文件和数据文件是分离的,索引文件仅保存记录所在页的指针(物理位置),通过这些地址来读取页,进而读取被索引的行。下图是MyISAM的索引原理图:(为了简化,一个页内只存放了两条记录。)

这里写图片描述

上图所提供的示例表字段有Col1(ID)、Col2(age)、Col3(name)三个,其中Col1为Primary Key(主键),上图很好地说明了树中叶子保存的是对应行的物理位置。通过该值,存储引擎能顺利地进行回表查询,得到一行完整记录。同时,每个叶子页也保存了指向下一个叶子页的指针。从而方便叶子节点的范围遍历。 
而对于二级索引,在 MyISAM存储引擎中以与上图同样的方式实现,这也说明了 MyISAM的索引方式是“非聚集的”,与 Innodb的“聚集索引”形成了对比。

InnoDB索引的实现

聚集索引

与 MyISAM相同的一点是,InnoDB 也采用 B+Tree这种数据结构来实现 B-Tree索引。而很大的区别在于,InnoDB 存储引擎采用“聚集索引”的数据存储方式实现B-Tree索引,所谓“聚集”,就是指数据行和相邻的键值紧凑地存储在一起,注意 InnoDB 只能聚集一个叶子页(16K)的记录(即聚集索引满足一定的范围的记录),因此包含相邻键值的记录可能会相距甚远。

在 InnoDB 中,表被称为 索引组织表(index organized table),InnoDB 按照主键构造一颗 B+Tree (如果没有主键,则会选择一个唯一的并且非空索引替代,如果没有这样的索引,InnoDB则会隐式地定义一个主键来作为聚集索引),同时叶子页中存放整张表的行记录数据,也可以将聚集索引的叶子节点称为数据页,非叶子页可以看做是叶子页的稀疏索引。

下图说明了 InnoDB聚集索引的实现方式,同时也体现了一张 innoDB表的结构,可以看到,InnoDB 中,主键索引和数据是一体的,没有分开。:

这里写图片描述

这种实现方式,给予了 InnoDB 按主键检索的超高性能。可以有目的性地选择聚集索引,比如一个邮件表,可以选择用户ID来聚集数据,这样只需要从磁盘读取较少并且连续的数据页就能获得某个id的用户全部的邮件,避免了读取分散页时所耗费的随机I/O。

辅助索引

而对于辅助索引,InnoDB采用的方式是在叶子页中保存主键值,通过这个主键值来回表(上图)查询到一条完整记录,因此按辅助索引检索实际上进行了二次查询,效率肯定是没有按照主键检索高的。下图是辅助索引的实现方式:

这里写图片描述

由于每个辅助索引都包含主键索引,因此,为了减小辅助索引所占空间,我们通常希望 InnoDB 表中的主键索引尽量定义得小一些(值得一提的是,MySIAM会使用前缀压缩技术使得索引变小,而InnoDB按照原数据格式进行存储。),并且希望InnoDB的主键是自增长的,因为如果主键并非自增长,插入时,由于写入时乱序的,会使得插入效率变低。

最后,我们要知道,B-Tree索引适用于等值匹配、范围匹配、键前缀匹配,这里的前缀指的是最左前缀。 
.

另附两篇很详细的文章: 
http://mp.weixin.qq.com/s?__biz=MjM5NzAzMTY4NQ==&mid=2653929459&idx=1&sn=7c6b55a461b816934c11855002f331f4&chksm=bd3b25998a4cac8fc1b86145f2bc98650192bdb1d18d4423956cbb0134f203208348f821eef1&scene=0#wechat_redirect

http://mp.weixin.qq.com/s/lwHsP0WVgtxRqynnjgy2ng

tags: Mysql,索引,innodb