标签：f1 Tree 查询 索引 MySQL 数据结构 节点

目录

• 1 索引数据结构
  • 1.1 索引数据结构介绍
  • 1.2 索引底层实现
    • 1.2.1 Hash索引
    • 1.2.2 B-Tree索引(MySQL使用B+Tree)
    • 1.2.3 B+Tree索引
      • 3.2.3.1 B+Tree性质
      • 1.2.3.2 一棵B+树可以存多少数据量
    • 1.2.4 Hash索引和B+树索引区别
    • 1.2.5 MyISAM和InnoDB实现B+树索引方式区别
    • 1.2.6 Mysql用B+树做索引而不用B-树或红黑树、二叉树
  • 1.3 聚簇索引和非聚簇索引
    • 1.3.1 聚簇索引
    • 1.3.2 非聚簇索引
    • 1.3.3 非聚簇索引一定会回表查询
  • 1.4 覆盖索引
  • 1.5 联合索引数据结构分析
    • 1.5.1 联合索引数据结构
    • 1.5.2 索引跳跃扫描
    • 1.5.3 优化原理
    • 1.5.4 限制条件

1 索引数据结构

1.1 索引数据结构介绍

索引是一种数据结构，可以帮助我们快速的进行数据的查找
索引的数据结构和具体存储引擎的实现有关，在 MySQL 中使用较多的索引有 Hash 索引，B+ 树索引等，而我们经常使用的 InnoDB 存储引擎的默认索引实现为：B+ 树索引

那么为什么使用索引：

• 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
• 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
• 帮助服务器避免排序和临时表。
• 将随机IO变为顺序IO。
• 可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义

1.2 索引底层实现

1.2.1 Hash索引

基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），并且Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针

1.2.2 B-Tree索引(MySQL使用B+Tree)

B-Tree能加快数据的访问速度，因为存储引擎不再需要进行全表扫描来获取数据，数据分布在各个节点之中。

1.2.3 B+Tree索引

B+Tree索引是B-Tree的改进版本，同时也是数据库索引所采用的存储结构。数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高

3.2.3.1 B+Tree性质

n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。

所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

所有的非终端结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
B+ 树中，数据对象的插入和删除仅在叶节点上进行。
B+树有2个头指针，一个是树的根节点，一个是最小关键码的叶节点。

点击了解二叉树中B+树数据结构

1.2.3.2 一棵B+树可以存多少数据量

大家是否还记得，一个B+树大概可以存放多少数据量呢？
InnoDB存储引擎最小储存单元是页，一页大小就是16k。
B+树叶子存的是数据，内部节点存的是键值+指针。索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而再去数据页中找到需要的数据；

假设B+树的高度为2的话，即有一个根结点和若干个叶子结点。这棵B+树的存放总记录数=根结点指针数*单个叶子节点记录行数。
如果一行记录的数据大小为1k，那么单个叶子节点可以存的记录数 =16k/1k =16
非叶子节点内存放多少指针呢？我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，所以就是8+6=14字节，16k/14B =16*1024B/14B = 1170
因此，一棵高度为2的B+树，能存放1170 * 16=18720条这样的数据记录。同理一棵高度为3的B+树，能存放1170 *1170 *16 =21902400，也就是说，可以存放两千万左右的记录。B+树高度一般为1-3层，已经满足千万级别的数据存储。

如果B+树想存储更多的数据，那树结构层级就会更高，查询一条数据时，需要经历的磁盘IO变多，因此查询性能变慢。

1.2.4 Hash索引和B+树索引区别

首先要知道 Hash 索引和 B+ 树索引的底层实现原理：

• hash索引底层就是 hash表，进行查找时，调用一次 hash函数就可以获取到相应的键值，之后进行回表查询获得实际数据。
• B+ 树底层实现是多路平衡查找树。对于每一次的查询都是从根节点出发，查找到叶子节点方可以获得所查键值，然后根据查询判断是否需要回表查询数据。

那么可以看出他们有以下的不同：

• hash索引进行等值查询更快(一般情况下)，但是却无法进行范围查询。
  因为在 hash索引中经过 hash函数建立索引之后，索引的顺序与原顺序无法保持一致，不能支持范围查询。而 B+树的的所有节点皆遵循(左节点小于父节点，右节点大于父节点，多叉树也类似)，天然支持范围。
• hash索引不支持使用索引进行排序，原理同上。
• hash索引不支持模糊查询以及多列索引的最左前缀匹配。原理也是因为 hash函数的不可预测。
• hash索引任何时候都避免不了回表查询数据,而B+树在符合某些条件(聚簇索引,覆盖索引等)的时候可以只通过索引完成查询。
• hash索引虽然在等值查询上较快，但是不稳定。性能不可预测，当某个键值存在大量重复的时候，发生 hash碰撞，此时效率可能极差。而 B+树的查询效率比较稳定，对于所有的查询都是从根节点到叶子节点，且树的高度较低。

因此，在大多数情况下，直接选择 B+ 树索引可以获得稳定且较好的查询速度。而不需要使用 hash索引

1.2.5 MyISAM和InnoDB实现B+树索引方式区别

MyISAM，B+Tree叶节点的data域存放的是数据记录的地址，在索引检索的时候，首先按照B+Tree搜索算法搜索索引，如果指定的key存在，则取出其data域的值，然后以data域的值为地址读取相应的数据记录，这被称为非聚簇索引

InnoDB，其数据文件本身就是索引文件，相比MyISAM，索引文件和数据文件是分离的，其表数据文件本身就是按B+Tree组织的一个索引结构，树的节点data域保存了完整的数据记录，这个索引的key是数据表的主键。
因此，InnoDB表数据文件本身就是主索引，这被称为聚簇索引或者聚集索引，而其余的索引都作为辅助索引，辅助索引的data域存储相应记录主键的值而不是地址，这也是和MyISAM不同的地方。

在根据主键索引搜索时，直接找到key所在的节点即可取出数据；根据辅助索引查找时，则需要先取出主键的值，再走一遍主索引。
因此，在设计表的时候，不建议使用过长的字段为主键，也不建议使用非单调的字段作为主键，这样会造成主索引频繁分裂。

总结：
InnoDB 主键索引使用的是聚簇索引，MyISAM 不管是主键索引，还是二级索引使用的都是非聚簇索引

1.2.6 Mysql用B+树做索引而不用B-树或红黑树、二叉树

主要原因：B+树只要遍历叶子节点就可以实现整棵树的遍历，而且在数据库中基于范围的查询是非常频繁的，而B树只能中序遍历所有节点，效率太低。

• B+树
  B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B(B-)树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
  由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

• Hash
  虽然可以快速定位，但是没有顺序，IO复杂度高；
  基于Hash表实现，只有Memory存储引擎显式支持哈希索引 ；
  适合等值查询，如=、in()、<=>，不支持范围查询 ；
  因为不是按照索引值顺序存储的，就不能像B+Tree索引一样利用索引完成排序 ；
  Hash索引在查询等值时非常快 ；
  因为Hash索引始终索引的所有列的全部内容，所以不支持部分索引列的匹配查找 ；
  如果有大量重复键值得情况下，哈希索引的效率会很低，因为存在哈希碰撞问题

• 二叉树
  树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高

• 红黑树
  树的高度随着数据量增加而增加，IO代价高

1.3 聚簇索引和非聚簇索引

1.3.1 聚簇索引

一种索引，该索引中键值的逻辑顺序决定了表中相应的物理顺序。
聚集索引确定表中数据的物理顺序。由于聚集索引规定数据在表中的物理存储顺序，因此 一个表只能包含一个聚集索引 。但该索引可以包含多个列（组合索引）

聚簇索引就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的就是整张表的行记录数据。

在 InnoDB 中，只有 主键索引是聚簇索引，如果没有主键，则挑选一个唯一键建立聚簇索引。如果没有唯一键，则MySQL自动为InnoDB表生成一个隐含字段来建立聚簇索引，这个字段长度为6个字节，类型为长整形。

当查询使用聚簇索引时，在对应的叶子节点，可以获取到整行数据，因此 不用再次进行回表查询

聚集索引图示
聚集索引的叶节点就是数据节点

1.3.2 非聚簇索引

一种索引，该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同。

索引是通过二叉树的数据结构来描述的，我们可以这么理解聚簇索引：索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点，只不过有一个指针指向对应的数据块

聚簇索引和非聚簇索引的区别：

• 聚簇索引的叶子节点存放的是主键值和数据行，支持覆盖索引。
• 非聚簇索引的叶子节点存放的是主键值或数据记录的地址(InnoDB辅助索引的data域存储相应记录主键的值，MyISAM辅助索引的data域保存数据记录的地址)

1.3.3 非聚簇索引一定会回表查询

非聚簇索引一定会回表查询吗
不一定，这涉及到查询语句所要求的字段是否全部命中了索引，如果全部命中了索引，那么就不必再进行回表查询。

举个简单的例子，假设我们在员工表的年龄上建立了索引，那么当进行select age from employee where age < 20的查询时，在索引的叶子节点上，已经包含了age信息，不会再次进行回表查询

1.4 覆盖索引

如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称 之为覆盖索引
我们知道在InnoDB存储引 擎中，如果不是主键索引，叶子节点存储的是主键值。最终还是要回表，也就是要通过主键再查找一次,这样就 会比较慢。覆盖索引就是把要查询出的列和索引是对应的，不做回表操作

转载于：https://mp.weixin.qq.com/s/gsA6lwUrL-1EvXRJdjlyFA

1.5 联合索引数据结构分析

1.5.1 联合索引数据结构

我们都知道，MySQL的Innodb引擎中，索引是通过B+树来实现的。不管是普通索引还是联合索引，都需要构造一个B+树的索引结构。

那么，我们都知道普通索引的存储结构中在B+树的每个非节点上记录的索引的值，而这棵B+树的叶子节点上记录的是聚簇索引（主键索引）的值。
如：

那么，如果是联合索引的话，这棵B+树又是如何存储的呢？
在联合索引中，联合索引(name,age)也是一个B+树，非叶子节点中记录的是name,age两个字段的值，叶子节点中记录的是name，age两个字段以及主键id的值

在存储的过程中，如上图所示，当age不同时，按照age排序，当age相同时，则按照name排序。

所以，了解了索引的存储结构之后，我们就很容易理解最左前缀匹配了：因为索引底层是一个B+树，如果是联合索引的话，在构造B+树的时候，会先按照左边的key进行排序，左边的key相同时再依次按照右边的key排序

所以，在通过索引查询的时候，也需要遵守最左前缀匹配的原则，也就是需要从联合索引的最左边开始进行匹配，这时候就要求查询语句的where条件中，包含最左边的索引的值。
在了解了最左前缀匹配之后，日常我们在工作中，经常在简历索引以及查询的时候，都会基于这个默认的约定进行索引的设计和SQL的优化。

大家都默认MySQL一定是遵循最左前缀匹配的。会认为当一个age,name的联合索引存在时，如果查询语句中不包含age作为条件，就一定不走索引。

MySQL一定是遵循最左前缀匹配的，这句话在以前是正确的，没有任何毛病。但是在MySQL 8.0中，就不一定了。

1.5.2 索引跳跃扫描

MySQL 8.0.13版本中，对于range查询，引入了索引跳跃扫描（Index Skip Scan）优化，支持不符合组合索引最左前缀原则条件下的SQL，依然能够使用组合索引，减少不必要的扫描。

通过一个例子给大家解释一下，首先有下面这样一张表（参考了MySQL官网的例子，但是我做了些改动和优化）：

创建表结构
create table t1(f1 int not null,f2 int not null);
创建联合索引
create index idx_t on t1(f1,f2);
插入数据
insert into t1 values
(1,1),(1,2),(1,3),(1,4),(1,5),
(2,1),(2,2),(2,3),(2,4),(2,5);

insert into t1 select f1,f2+5 from t1;
insert into t1 select f1,f2+10 from t1;
insert into t1 select f1,f2+20 from t1;
insert into t1 select f1,f2+40 from t1;

分别在MySQL 5.7.9和MySQL 8.0.30上执行：

explain select f1,f2 from t1 where f2=40;

执行结果如下：

可以看到，主要有以下几个区别：

MySQL 5.7中，type = index，rows=160，extra=Using where;Using index
MySQL 8.0中，type = range，rows=16，extra=Using where;Using index for skip scan

这里面的type指的是扫描方式，range表示的是范围扫描，index表示的是索引树扫描，通常情况下，range要比index快得多。

从rows上也能看得出来，使用index的扫描方式共扫描了160行，而使用range的扫描方式只扫描了16行。

接着，重点来了，那就是为啥MySQL 8.0中的扫描方式可以更快呢？主要是因为Using index for skip scan表示他用到了索引跳跃扫描的技术

也就是说，虽然我们的SQL中，没有遵循最左前缀原则，只使用了f2作为查询条件，但是经过MySQL 8.0的优化以后，还是通过索引跳跃扫描的方式用到了索引了。

1.5.3 优化原理

在MySQL 8.0.13及以后的版本中

SELECT f1, f2 FROM t1 WHERE f2 = 40;

SQL执行过程如下：

• 获取f1字段第一个唯一值，也就是f1=1
• 构造f1=1 and f2 = 40，进行范围查询
• 获取f1字段第二个唯一值，也就是f1=2
• 构造f1=2 and f2 = 40，进行范围查询
• 一直扫描完f1字段所有的唯一值，最后将结果合并返回

也就是说，最终执行的SQL语句是像下面这样的：

SELECT f1, f2 FROM t1 WHERE f1=1 and f2 = 40
union
SELECT f1, f2 FROM t1 WHERE f1=2 and f2 = 40

即，MySQL的优化器帮我们把联合索引中的f1字段作为查询条件进行查询了。

1.5.4 限制条件

在知道了索引跳跃扫描的执行过程之后，这种查询优化比较适合于f1的取值范围比较少，区分度不高的情况，一旦f1的区分度特别高的话，这种查询可能会更慢。
所以，真正要不要走索引跳跃扫描，还是要经过MySQL的优化器进行成本预估之后做决定的。

所以，这种优化一般用于那种联合索引中第一个字段区分度不高的情况。但是话又说回来了，我们一般不太会把区分度不高的字段放在联合索引的左边，不过事无绝对，既然MySQL给了一个优化的方案，就说明还是有这样的诉求的。
但是，我们不能依赖他这个优化，建立索引的时候，还是 优先把区分度高的，查询频繁的字段放到联合索引的左边

除此之外，在MySQL官网中，还提到索引跳跃扫描还有一些其他的限制条件：

• 表T至少有一个联合索引，但是对于联合索引(A,B,C,D)来说，A和D可以是空的，但B和C必须是非空的。
• 查询必须只能依赖一张表，不能多表JOIN
• 查询中不能使用GROUP BY或DISTINCT语句
• 查询的字段必须是索引中的列

联合索引最左匹配原则参考链接

标签：f1,Tree,查询,索引,MySQL,数据结构,节点
From： https://www.cnblogs.com/jingzh/p/16975435.html