扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 计算机基础 > MySQL高频面试题 > 6.MySQL索引的数据结构?

MySQL索引的数据结构主要有B+树哈希表,对应的索引分别为B+树索引和哈希索引。InnoDB引擎的索引类型有B+树索引和哈希索引,默认的索引类型为B+树索引

  • B+树索引

熟悉数据结构的同学都知道,B+树、平衡二叉树、红黑树都是经典的数据结构。在B+树中,所有的记录节点都是按照键值大小的顺序放在叶子节点上,如下图。

B+树-聚簇索引
B+树-聚簇索引


从上图可以看出 ,因为B+树具有有序性,并且所有的数据都存放在叶子节点,所以查找的效率非常高,并且支持排序和范围查找。

B+树的索引又可以分为主索引和辅助索引。其中主索引为聚簇索引,辅助索引为非聚簇索引。聚簇索引是以主键作为B+ 树索引的键值所构成的B+树索引,聚簇索引的叶子节点存储着完整的数据记录;非聚簇索引是以非主键的列作为B+树索引的键值所构成的B+树索引,非聚簇索引的叶子节点存储着主键值。所以使用非聚簇索引进行查询时,会先找到主键值,然后到根据聚簇索引找到主键对应的数据域。上图中叶子节点存储的是数据记录,为聚簇索引的结构图,非聚簇索引的结构图如下:

B+树-非聚簇索引
B+树-非聚簇索引
  • 哈希索引

哈希索引是基于哈希表实现的,对于每一行数据,存储引擎会对索引列通过哈希算法进行哈希计算得到哈希码,并且哈希算法要尽量保证不同的列值计算出的哈希码值是不同的,将哈希码的值作为哈希表的key值,将指向数据行的指针作为哈希表的value值。这样查找一个数据的时间复杂度就是o(1),一般多用于精确查找。