索引底层数据结构的探索

索引可选的数据结构 :

  • 二叉树
  • 红黑树
  • hash
  • B Tree

mysql索引的底层用的并不是二叉树和红黑树。因为二叉树和红黑树在某些场景下都会暴露出一些弊端或者说缺点。

二叉树在某些场景下退化成了链表。
红黑树某些时候高度会很大，树的高度过高导致查询效率变慢。

B-Tree

  • 叶节点具有相同的深度，叶节点的指针为空
  • 所有索引元素不重复
  • 节点中的数据索引从左到右递增排序
    image.png

B+Tree

  • 非叶子节点不存储data，只存储索引（冗余），可以放更多的索引
  • 叶子节点包含所有索引字段
  • 叶子节点用指针连接，提高区间访问的性能
    image.png

和B-Tree的区别是，非叶子节点没有数据，数据都挪到叶子节点，叶子节点之间还有指针。非叶子节点之间跟原来一样没有指针。

非叶子节点只存储索引元素，叶子节点存储了一份完整表的所有行的索引字段，data元素是每个索引元素对应要查找的行记录的位置或行数据，这样非叶子节点的每个节点就可以存储更多的索引元素（等会会有一个大致的估算）

B树由于所有的节点都可能包含目标数据，我们总是要从根节点向下遍历子树查找满足条件的数据行，这个特点带来了大量的随机 I/O，也是B树最大的性能问题。

B+ 树中就不存在这个问题了，因为所有的数据行都存储在叶节点中，而这些叶节点可以通过『指针』依次按顺序连接，当我们在如下所示的 B+ 树遍历数据时可以直接在多个子节点之间进行跳转，这样能够节省大量的磁盘 I/O 时间，也不需要在不同层级的节点之间对数据进行拼接和排序；通过一个 B+ 树最左侧的叶子节点，我们可以像链表一样遍历整个树中的全部数据，我们也可以引入双向链表保证倒序遍历时的性能。
image.png

真实情况在innodb中，是使用双向链表。

页的概念

Mysql的innodb是以页为存储单位的，每个B+Tree的叶子节点都是一个页的大小的倍数，默认一页的大小是16K
页结构如下图所示
image
也就是每一个页都包含两个页指针，一个是previous page指针，指向上一个页，一个是next page指针，指向下一个页。
头部还有Page的类型信息和用来唯一标识Page的编号。根据这个指针分布可以想象到Page链接起来就是一个双向链表。
如下图所示
image-1648875902280
由于一个B+Tree的叶子节点是一个页，所以每个叶子节点之间是一个双向链表的结构
image-1648876094899

有些人可能会认为使用 B+ 树这种数据结构会增加树的高度从而增加整体的耗时，然而高度为 3 的 B+ 树就能够存储千万级别的数据，实践中 B+ 树的高度最多也就 4 或者 5，所以这并不是影响性能的根本问题。

从今天的角度来看，B+ 树可能不是 InnoDB 的最优选择，但是它一定是能够满足当时设计场景的需要，从 B+ 树作为数据库底层的存储结构到今天已经过了几十年的时间，我们不得不说优秀的工程设计确实有足够的生命力。而我们作为工程师，在选择数据库时也应该非常清楚地知道不同数据库适合的场景，因为软件工程中没有银弹。

聚簇索引和非聚簇索引

聚簇索引和非聚簇索引是B+树的具体体现，这两种索引本质上都是一棵B+树，只是叶子结点存储的数据不一样。
InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分（MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址）
聚簇索引(也称为主键索引)就是携带了行数据的索引，非聚簇索引就是除了聚簇索引之外的索引

每个InnoDB表都有一个特殊的索引，称为聚簇索引，用于存储行数据。

  1. 如果创建了一个主键，InnoDB会将其用作聚簇索引(如果主键没有逻辑唯一且非空的列或列集，最好是设置成自动递增的)
  2. 如果没有为表创建主键，则MySQL会在所有键列都不为NULL的情况下找到第一个UNIQUE索引，InnoDB会将其用作聚集索引
  3. 如果表没有PRIMARY KEY或合适的UNIQUE索引，则InnoDB在包含行ID值的合成列上内部生成一个名为GEN_CLUST_INDEX的隐藏的聚集索引(隐藏的是看不到的，也就是说不会出现在desc table中，行ID是一个6字节的字段，随着插入新行而单调增加)

从这三种情况来看的话，就是说不管你有没有创建主键，mysql都会给你弄一个聚簇索引给安排上，你创建了就用你设置的主键为聚簇索引，没有创建就给你来个隐藏的。

image-1649775534919
可以看到聚簇索引后面是直接跟着的数据，而非聚簇索引除了有索引的数据之外，还有指向的是聚簇索引的key值。

因此非聚簇索引查询数据需要先查到聚簇索引的key，然后用这个key去查询真正的数据(这个过程称为回表)。

也就是说非聚簇索引是需要查询两次

所以能走聚簇索引的尽量走聚簇索引(也可以说是尽量走主键)，看起来都是走索引，实际上主键要更快。

而且主键索引如果是自增的int类型，因为长度比较小，占用的空间也比较小。

联合索引在B+树上的存储结构及数据查找方式

联合索引是B+树上结点的一种数据组合方式。
首先，表T1有字段a,b,c,d,e，其中a是主键，创建了一个联合索引idx_t1_bcd(b,c,d)，然后b、c、d三列作为联合索引，在B+树上的结构正如上图所示。联合索引的所有索引列都出现在索引树上，并依次比较三列的大小。
image.png

对于联合索引来说只不过比单值索引多了几列，而这些索引列全都出现在索引树上。对于联合索引，存储引擎会首先根据第一个索引列排序，如上图我们可以单看第一个索引列，横着看，如，1 1 5 12 13…他是单调递增的；如果第一列相等则再根据第二列排序，依次类推就构成了上图的索引树，上图中的b列都等于1时，则根据c排序，此时c列也相等则按d列排序，如：1 1 4 ，1 1 5，c=4在c=5前面，以及13 12 4,13 16 1,13 16 5就可以说明这种情况。

联合索引的查找方式

image.png

最左前缀匹配原则

联合索引是首先使用多列索引的第一列构建的索引树，用上面idx_t1_bcd(b,c,d)的例子就是优先使用b列构建，当b列值相等时再以c列排序，若c列的值也相等则以d列排序。我们可以取出索引树的叶子节点看一下
image.png

索引的第一列也就是b列可以说是从左到右单调递增的，但我们看c列和d列并没有这个特性，它们只能在b列值相等的情况下这个小范围内递增，如第一叶子节点的第1、2个元素和第二个叶子节点的后三个元素。
​
由于联合索引是上述那样的索引构建方式及存储结构，所以联合索引只能从多列索引的第一列开始查找。所以如果你的查找条件不包含b列如（c,d）、(c）、(d)是无法应用缓存的，以及跨列也是无法完全用到索引如(b,d)，只会用到b列索引。

覆盖索引

我们上面说到如果是非聚簇索引的话会需要回表，查询两次，但是如果要查询得字段，数据直接就在索引上是可以不需要回表的。这种索引称为覆盖索引。

比如我们要查询表中的age和name两个字段。
select id，age，name from test where age = 13;
直接查询的话，会根据age的索引找到id的key，然后再用id去查询出数据。

但是如果我们创建一个(age，name)的联合索引，情况就不一样了。
image-1649776015539

这个时候执行SELECT age FROM student WHERE name = '小李'时的查询步骤为：

  1. 在name,age联合索引树上找到名称为小李的节点
  2. 此时节点索引里包含信息age 直接返回12，不需要再回表

有联合索引存在的情况下能走覆盖索引当然是最好的，提高了查询效率

索引下推

在MySQL5.6版本以后，引入了索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，减少回表次数。
如果有这样一个查询语句where name like '张%' and age = 10，那么如果匹配到了张，会直接先匹配age，减少回表次数。

主键索引和唯一索引的区别

  1. 主键是一种约束，唯一索引是一种索引，两者在本质上是不同的。
  2. 主键创建后一定包含一个唯一性索引，唯一性索引并不一定就是主键。
  3. 唯一性索引列允许空值，而主键列不允许为空值。
  4. 主键可以被其他表引用为外键，而唯一索引不能。
  5. 一个表最多只能创建一个主键，但可以创建多个唯一索引。
  6. 主键更适合那些不容易更改的唯一标识，如自动递增列、身份证号等。
  7. 在RBO模式下，主键的执行计划优先级要高于唯一索引。 两者可以提高查询的速度。约束主要有：主键约束、外键约束、非空约束、检查约束（bentwen and ，大于、小于、等于、不等于）、唯一约束。

建索引的几大原则

  1. 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。

  2. =和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式

  3. 尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录

  4. 索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);

  5. 尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可

为什么 MySQL 使用 B+ 树
联合索引在B+树上的存储结构及数据查找方式
mysql聚簇索引和非聚簇索引
MySQL数据库中innodb引擎的B+Tree的底部到底时单向链表还是双向链表