索引的实现原理 B+tree
视频版-看着更方便:
哔哩哔哩 👉 https://b23.tv/zVjcO3x
小红书 👉 http://xhslink.com/HAW2ai
之前我讲了 树结构 的入门款 二叉树
而今天要说的 B+tree 则是专为 索引 而生的
基于 二叉树的一种变种树
那么 B+tree 也就是索引到底长啥样呢?
接下来我就用表数据来模拟一下:
B+tree
假设有这样一张表:
此时如果以 id 作为主键构建索引
做成的B+tree就是这样的:
于是正常情况 如果查询 id 为 7 的数据
数据库从上到下遍历需要查 6 次
而使用索引则只需要 3 次即可
有了 B+tree 数据结构的支持
查询算法确实更快了
为什么用 B+tree 而不是 二叉树
我们回看这个B+tree的结构
它和二叉树的区别在于
它是一种 多叉树
这种多叉的设计有什么好处呢?
在表数据量相同的情况下
多叉 的B+tree 层树更少
我们知道程序加载 树结构 的方式为:
每次加载子节点都需要和磁盘进行一次I/O
而磁盘I/O要比内存慢的多
因此 多叉的 B+tree 能够减少磁盘I/O次数
进而提升查询速度。
这就是索引 使用B+tree的原因了
ok 那了解了 索引的原理 以及B+tree 结构之后
我们继续研究一下:
不同类型的索引
->主键索引
顾名思义 围绕主键字段建立的索引
以mysql为例
当我们执行表创建语句的时候
CREATE TABLE `T` (
`id` int(10) NOT NULL,
`name` varchar(32) DEFAULT NULL,
`yanzhi` int(11) DEFAULT NULL,
PRIMARY KEY (`id`),
) ENGINE=InnoDB
innodb存储引擎会默认以主键作为索引
将表直接以 B+tree 的形式存储
也就是视频开头的例子
在最底层的叶子节点中直接保存了索引字段所在行的完整数据
像这种 将表的完整数据直接聚集在B+tree上的索引 又叫做 聚簇索引
那与之对应的另一种索引就叫做 非聚簇索引
也就是 非主键索引、二级索引
->非主键索引、二级索引
还是这个表
这次我们围绕 yanzhi 字段建立 非主键索引
对比 主键索引 来看
区别在于
非主键索引 最底层的叶子节点保存的并不是完整的行数据
而是 主键字段
所以当我们对非主键索引进行查询的时候
首先需要在非主键索引上拿到主键id
然后根据主键id再去查询主键索引
这个 回查主键索引 的过程书本上称之为 回表
我们浅想一下 回表 不是什么好事 对不对
因为要查两次索引 会影响查询效率
于是我们再回看一下这个非主键索引奥
既然你只能找到主键id
那我只查id:
select id from T where yanzhi = 60
这样就不用回表了吧
像这样 只通过非主键索引一次得到查询结果
而将 回表 操作覆盖了的现象书本上就叫做 ”覆盖索引“
注意奥!!!
覆盖索引 它不是索引类型,它是 能够避免 回表 的一种优化思路。
在实际应用中 你可以使用 联合索引 + 覆盖索引 来优化查询语句
下面我用例子来演示一下应用的过程:
联合索引 + 覆盖索引
假设我现在想根据姓名查询颜值
select yanzhi from T where name = '刘*菲'
首先
围绕 姓名 和 颜值 建立联合索引
create index name_yanzhi on T(name, yanzhi);
联合索引 也是 索引类型的一种
它遵循 最左匹配 原则
什么意思呢?
如果a,b,c为联合索引字段
那么你的where条件只有
a
a and b
a and b and c
这三种搭配才会走索引
如果是
b
b and c
或
c
是不会走索引的
那你可能会问
a and b
a and b and c
调换字段顺序会走索引吗
答案是肯定的
我在之前讲 查询sql的执行过程 那期提到过优化过程:
优化器 会 重新调整字段顺序以保证应用到索引
于是当我们用姓名为where条件时
select yanzhi from T where name = '刘*菲'
开始走联合索引
由于 索引中包含了 颜值字段
触发了 覆盖索引
不需要回表
查询效率就得到了优化
总结
我们以 索引 为主题
了解了 B+tree 数据结构
以及不同类型的 索引:
主键索引(聚簇索引)
非主键索引、联合索引(非聚簇索引)
并由此引出了 回表、覆盖索引 的概念
以及针对 回表 的优化方案:
联合索引 + 覆盖索引
我是浩说
帮你入门到放弃