转载~
在上一篇《索引基础知识回顾》中提到索引按照存储结构划分有B-Tree索引、Hash索引、B+Tree索引类型,接下来就学习一下这几种索引结构以及在实际存储引擎中的使用情况
「Hash底层是由Hash表来实现的,存储引擎都会【对所有的索引列计算一个哈希码】(hash code),哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针,根据键值 <key,value> 存储数据的结构存储<哈希码,指针>,非常适合根据key查找value值,也就是等值查询(单个key查询)」。其结构如下所示:
Hash索引在MySQL 中Hash结构主要应用在Memory原生的Hash索引 、InnoDB 自适应哈希索引。在《InnoDB的存储结构》已经介绍过自适应哈希索引,这里不再赘述。
「平衡多路查找树(B-Tree):是为磁盘等外存储设备设计的一种平衡查找树」。
「我们知道在InnoDB存储引擎中页是其磁盘管理的最小单位,默认是16KB,而系统一个磁盘块的存储空间没有这么大,因此InnoDB每次申请磁盘空间时都会申请若干地址连续磁盘块来达到页的大小16KB。在查询时如果数据都在一个页中,会减少磁盘I/O次数,提高查询效率。」
「B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块」。它每个节点根据实际情况可以包含大量的关键字信息和分支,下图为一个3阶的B-Tree:
由上图中可以看出B-Tree有如下「特征」:
模拟查找关键字29的过程:
通过以上过程,我们查找29,只需要三次IO,「而3阶的B-Tree可以容纳百万级数据,这对查询性能的提升是巨大的」。如果没有索引,每个数据项都要发生一次IO,总共需要百万次的IO,显然成本非常非常高。
「B+Tree是在B-Tree基础上的一种优化,使其更适合实现外存储索引结构,InnoDB存储引擎就是用B+Tree实现其索引结构」。
在上述中提到数据页的存储空间默认是16KB,而B-Tree结构图中可以看到每个节点中不仅包含数据的key值,还有data值。当数据较大时,一个节点(即一个页)能存储的key的数量就会很小,导致B-Tree的深度变大,增大查询时的磁盘I/O次数,进而影响查询效率。
对此,「B+Tree进行了优化,将所有数据都是按照键值大小顺序存放在同一层的叶子节点上,非叶子节点上只存储key值,以此增大每个节点存储的key值数量,降低B+Tree的高度」。下图为一个3阶的B+Tree:
通过示意图可以看出「B+Tree不仅仅将数据存放在叶子结点,而且所有叶子节点(数据节点)之间都有一个链指针,从而方便叶子节点的范围遍历」。特征如下:
「MySQL中索引属于存储引擎级别的概念,MyISAM和InnoDB都是使用B+Tree作为索引结构,但是不同存储引擎对索引的实现方式不同」。
在《存储引擎》一文中介绍到MyISAM针对每个表有两个文件:「一个.frm表结构文件,一个MYD表数据文件,一个.MYI索引文件」。数据和索引是分开存储的。
「MyISAM使用B+Tree作为索引结构时,.MYI索引文件的叶节点的data域存放的是数据记录的地址」。
按照示意图:MyISAM在索引检索时首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。
「在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复」。
在《存储引擎》一文中介绍到InnoDB针对每个表有两个文件:「一个.frm表结构文件,一个.ibd数据文件」,数据和索引是一起存储的,定位到了数据也就找到了数据。
「InnoDB的聚簇索引就是按照主键顺序构建 B+Tree结构。叶子节点data域存储了完整的数据记录,行记录和主键值紧凑地存储在一起。即 InnoDB 的主键索引就是数据表本身,它按主键顺序存放了整张表的数据,占用的空间就是整个表数据量的大小。」
「在InnoDB中,主索引和辅助索引(Secondary key)的Data域存储是不同的」,这与MyISAM是不同的。
如示意图所示,辅助索引索引中data域中存储的是主键,所以辅助索引一般需要两次查找才能查到数据: