索引的原理？？？B+tree（数据结构和算法）
索引的实现原理 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=InnoDBinnodb存储引擎会默认以主键作为索引
将表直接以 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 数据结构
以及不同类型的 索引：
主键索引（聚簇索引）
非主键索引、联合索引（非聚簇索引）
并由此引出了 回表、覆盖索引 的概念
以及针对 回表 的优化方案：
联合索引 + 覆盖索引
我是浩说
帮你入门到放弃