数据结构论坛

首页 » 分类 » 问答 » 终极面试InnoDB中BTree索引
TUhjnbcbe - 2021/3/12 1:30:00
数据库索引漫谈

前言

    大家在平时工作学习中,使用到索引的场景有非常多,比如查询缓慢等等场景,但是索引是什么东西?怎么使用索引?怎么才能命中索引?等等一系列问题提出时,是不是会懵一下,这篇文章就带大家研究下索引和命中率的一系列问题。

什么是索引

概念:索引是帮助数据库高效获取数据的排好序的数据结构。

从概念上讲数据库索引的本质是数据结构。(重要)

索引是表级别的,不是库级别的,最简单的例子就是在创建表的时候我们需要指定存储引擎。

索引分类

常见MySQL索引一般分为:Hash索引和B+Tree索引,InnoDB引擎,默认的是B+树。

我们可以看下hash索引和B+数图示:

B+树:

B+树是一个平衡的多叉树,从根节点到每个叶子节点的高度差值不超过1,而且同层级的节点间有指针相互链接。

在B+树上的常规检索,从根节点到叶子节点的搜索效率基本相当,不会出现大幅波动,而且基于索引的顺序扫描时,也可以利用双向指针快速左右移动,效率非常高。因此,B+树索引被广泛应用于数据库、文件系统等场景。

Hash:

哈希索引就是采用一定的哈希算法,把键值换算成新的哈希值,检索时不需要类似B+树那样从根节点到叶子节点逐级查找,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。

从上述图示中,我们可以发现:

哈希索引不适用的场景:

(1)不支持范围查询

(2)不支持索引完成排序

(3)不支持联合索引的最左前缀匹配规则

在等值查询的时候,哈希索引有很大的优势,但是有大量重复键值的时候,就会出现哈希碰撞问题(键值通过哈希计算后,会出现大量重复的键值,会拉出链表),降低效率。

所以,一般索引会采用B+树的数据结构。

面试题:索引为什么使用B+树而不是B树?(插播)

我们先看两张图,分别是B树和B+树:(来源互联网)

B树:

B+树:

我们分析下这两颗树:

1、B+树叶子节点之间可以互相访问,而B树不行;

2、B+树叶子节点保存了上层冗余节点,而B树没有保存;

3、B+只有叶子节点保存数据,而B树每个节点都保存数据;

综上所述,我们可以得出答案:

1、B+树节点不保存数据,所以磁盘页可以存储更多的节点元素,也就是更“矮胖”,减少IO操作;

2、b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定;

3、范围查找中,B+数可以遍历叶子节点,而B树需要重复的遍历

注:我们一般可以认为树的高度就是IO操作次数。

聚簇索引与非聚簇索引

我们一般说聚簇索引与非聚簇索引是针对于InnoDB引擎和MyISAM引擎;

聚簇索引与非聚簇索引最大的区别就是叶节点是否存放整行记录;(重点)

InnoDB主键索引使用的是聚簇索引,MyISAM使用的是非聚簇索引;

MyISAM索引

MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址(非聚簇索引);

非聚簇索引将数据存储于索引分开结构,索引结构的叶子节点指向了数据的对应行,myisam通过key_buffer把索引先缓存到内存中,当需要访问数据时(通过索引访问数据),在内存中直接搜索索引,然后通过索引找到磁盘相应数据;

图片来源互联网

MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址;

InnoDB索引

InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。(聚簇索引)

聚簇索引默认是主键,如果表中没有定义主键,InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引,InnoDB会隐式定义一个主键来作为聚簇索引。

图片来源互联网

聚簇索引与非聚簇索引的区别

来看一张图:(来源互联网)

1.非聚簇索引表(右图),表数据和索引是分成两部分存储的,主键索引和二级索引存储上没有任何区别。使用的是B+树作为索引的存储结构,所有的节点都是索引,叶子节点存储的是索引+索引对应的记录的数据。

2.聚簇索引表(左图),表数据是和主键一起存储的,主键索引的叶结点存储行数据(包含了主键值),二级索引的叶结点存储行的主键值。使用的是B+树作为索引的存储结构,非叶子节点都是索引关键字,但非叶子节点中的关键字中不存储对应记录的具体内容或内容地址。叶子节点上的数据是主键与具体记录(数据内容)。使用非主键索引,存储的是主键的值,然后通过主键获取主键索引,聚集索引存储行数据,通过主键索获取数据;回到主键索引树搜索的过程,称为回表。

说明

这篇文章参考了不少大家之作,最终形成这篇文章,感谢分享知识的广大工程师。文章如有错误或者不足之处,请大家多多指点,同时希望大家能有所收获~

点击蓝字·

1
查看完整版本: 终极面试InnoDB中BTree索引