乐趣区

关于b+树:联合索引在BTree上的存储结构及数据查找方式

jiezi

最艰难的事件就是意识本人！

集体网站，欢送拜访！

前言：

本篇文章次要是论述下 联结索引 在 B+Tree 上的理论存储构造。

本文次要解说的内容有：

  • 联结索引在 B + 树上的存储构造
  • 联结索引的查找形式
  • 为什么会有最左前缀匹配准则

在分享这篇文章之前，我在网上查了对于 MySQL 联结索引在 B + 树上的存储构造这个问题，翻阅了很多博客和技术文章，其中有几篇讲述的与事实相悖。具体如下：

很多博客中都是说：联结索引在 B + 树上的 非叶子节点 中只会存储 联结索引 中的第一个索引字段 的值，联结索引的其余索引字段的值只会呈现在 B+ 树 的 叶子节点 中。（其实这句话是不对的）

如下图，就是 谬误的 联结索引的 B+ 树 存储结构图：

庆幸的是通过一直查问发现有一条是来自思否社区的对于【联结索引 在 B+Tree 上的存储构造？】问答，有答主答复了这个问题，并贴出了一篇文章和一张图以及一句简略的形容。PS：贴出的文章链接曾经打不开了。

所以在这样的条件下本篇文章就诞生了。

联结索引存储构造：

上面就援用思否社区的这个问答来开展咱们明天要探讨的联结索引的存储构造的问题。

来自思否的发问，联结索引的存储构造
(https://segmentfault.com/q/10…
有码友答复如下：

联结索引 bcd , 在索引树中的样子如下图，在比拟的过程中，先判断 b 再判断 c 而后是 d：

因为答复只有这么一张图一句话，可能会让大家有点看不懂，所以咱们就借助前人的肩膀用这个例子来更加粗疏的讲探寻一下联结索引在 B + 树上的存储构造吧。

首先，有一个 T1 表，而后表 T1 有字段 a,b,c,d,e，其中 a 是主键，除 e 为 varchar 其余为 int 类型，并创立了一个联结索引 idx_t1_bcd(b,c,d)，而后 b、c、d 三列作为联结索引，在 B + 树上的构造正如上图所示。联结索引的所有索引列都呈现在索引数上，并顺次比拟三列的大小。上图树高只有两层不容易了解，上面是假如的表数据以及我对其联结索引在 B + 树上的结构图的改良。PS：基于 InnoDB 存储引擎。

index（b、c、d）联结索引在 B + 树上的结构图如下：

T1 表中的数据如下图：（上图 B+ 树 中的数据就来自下图）

通过这俩图咱们心里对联结索引在 B + 树上的存储构造就有了个大略的意识。上面用我的语言为大家解释一下吧。

咱们先看 T1 表，他的主键暂且咱们将它设为整型自增的，InnoDB 会应用主键索引在 B + 树保护索引和数据文件，而后咱们创立了一个联结索引（b，c，d）也会生成一个索引树，同样是 B + 树的构造，只不过它的 data 局部 存储的是联结索引所在行记录的主键值 （上图叶子节点紫色背景局部）。为什么是 主键值，而不是 整个行记录呢？因为这个 联结索引 是个 非聚簇索引。

好了大抵状况都介绍完了。上面咱们联合这俩图来解释一下。

对于联结索引来说只不过比单值索引多了几列，而这些索引列全都呈现在索引树上。对于联结索引，存储引擎会首先依据第一个索引列排序，如上图咱们能够单看第一个索引列，如，1 1 5 12 13…它是枯燥递增的；如果第一列相等则再依据第二列排序，顺次类推就形成了上图的索引树，上图中的 1 1 4，1 1 5 以及 13 12 4, 13 16 1, 13 16 5 就能够阐明这种状况。

联结索引具体查找步骤：

当咱们的 SQL 语言能够利用到索引的时候，比方 select * from T1 where b = 12 and c = 14 and d = 3；也就是 T1 表中 a 列为 4 的这条记录。

查找步骤具体如下：

  1. 存储引擎首先从根节点（个别常驻内存）开始查找，第一个索引的第一个索引列为 1,12 大于 1，第二个索引的第一个索引列为 56,12 小于 56，于是从这俩索引的两头读到下一个节点的磁盘文件地址（此处实际上是存在一个指针的，指向的是下一个节点的磁盘地位）。
  2. 进行一次磁盘 IO，将此节点值加载后内存中，而后依据第一步一样进行判断，发现 数据都是匹配的，而后依据指针将此联结索引值所在的叶子节点也从磁盘中加载后内存，此时又产生了一次磁盘 IO，最终依据叶子节点中索引值关联的 主键值。
  3. 依据主键值 回表 去主键索引树（聚簇索引）中查问具体的行记录。

联结索引的最左前缀准则：

之所以会有最左前缀匹配准则和联结索引的索引构建形式及存储构造是有关系的。

首先咱们创立的 idx_t1_bcd(b,c,d)索引，相当于创立了(b)、（b、c）（b、c、d）三个索引，看完上面你就晓得为什么相当于创立了三个索引。

咱们看，联结索引是首先应用多列索引的第一列构建的索引树，用下面 idx_t1_bcd(b,c,d)的例子就是优先应用 b 列构建，当 b 列值相等时再以 c 列排序，若 c 列的值也相等则以 d 列排序。咱们能够取出索引树的叶子节点看一下。

索引的第一列也就是 b 列能够说是从左到右枯燥递增的，但咱们看 c 列和 d 列并没有这个个性，它们只能在 b 列值相等的状况下这个小范畴内递增，如第一叶子节点的第 1、2 个元素和第二个叶子节点的后三个元素。
​
因为联结索引是上述那样的索引构建形式及存储构造，所以联结索引只能从多列索引的第一列开始查找。所以如果你的查找条件不蕴含 b 列如（c,d）、(c）、(d)是无奈利用缓存的，以及跨列也是无奈齐全用到索引如(b,d)，只会用到 b 列索引。

这就像咱们的电话本一样，有名和姓以及电话，名和姓就是联结索引。在姓能够以姓的首字母排序，姓的首字母雷同的状况下，再以名的首字母排序。

如：

M
    毛 不易   178********
    马 化腾   183********
    马 云     188********
Z
    张 杰     189********
    张 靓颖   138********
    张 艺兴   176********

咱们晓得名和姓是很快就可能从姓的首字母索引定位到姓，而后定位到名，进而找到电话号码，因为所有的姓从上到下依照既定的规定（首字母排序）是有序的，而名是在姓的首字母肯定的条件下也是依照名的首字母排序的，然而整体来看，所有的名放在一起是无序的，所以如果只晓得名查找起来就比较慢，因为无奈用已排好的构造疾速查找。

到这里大家是否明确了为啥会有最左前缀匹配准则了吧。

实际：

如下列举一些 SQL 的索引应用状况：

select * from T1 where b = 12 and c = 14 and d = 3;-- 全值索引匹配 三列都用到
select * from T1 where b = 12 and c = 14 and e = 'xml';-- 利用到两列索引
select * from T1 where b = 12 and e = 'xml';-- 利用到一列索引
select * from T1 where b = 12  and c >= 14 and e = 'xml';-- 利用到一列索引及索引条件下推优化
select * from T1 where b = 12  and d = 3;-- 利用到一列索引  因为不能跨列应用索引 没有 c 列 连不上
select * from T1 where c = 14  and d = 3;-- 无奈利用索引，违反最左匹配准则

后记：

到这里 MySQL 索引的联结索引的存储构造及查找形式就讲完了，自己能力无限，也是站着前人的肩膀上创作的此文，因为看到搜索引擎的搜寻后果前几个技术文章中有存在讲述不清或讲述有误的中央，所以本人才总结出这篇文章分享给大家，如有不对的中央肯定要斧正哦，谢谢了。

这篇文章断断续续利用工作之余画图加写作用了两三天，次要内容就是下面这些了。不可否认，这篇文章在肯定水平上有夸夸其谈之嫌，因为我自己对 MySQL 的应用属于菜鸟级别，更没有太多数据库调优的教训，在这里高谈阔论实属羞愧。就当是我集体的一篇学习笔记了。

另外，MySQL 索引及常识十分宽泛，本文只是波及到其中一部分。如与排序（ORDER BY）相干的索引优化及笼罩索引（Covering index）的话题本文并未波及，同时除 B -Tree 索引外 MySQL 还依据不同引擎反对的哈希索引、全文索引等等本文也并未波及。如果有机会，心愿再对本文未波及的局部进行补充吧。

❤不要遗记留下你学习的脚印 [点赞 + 珍藏 + 评论]嘿嘿ヾ

所有看文章不点赞都是“耍流氓”，嘿嘿ヾ (◍°∇°◍)ﾉﾞ！开个玩笑，动一动你的小手，点赞就完事了，你每个人出一份力量(点赞 + 评论) 就会让更多的学习者退出进来！非常感谢！~ω~=

退出移动版