乐趣区

关于mysql:mysql-索引

jiezi

为什么 mysql 应用 B + 树作为索引

索引的呈现其实就是为了进步数据查问的效率.

就像书的目录一样。一本 500 页的书，如果你想疾速找到其中的某一个知识点，咱们必定要先依据目录找到某个章节。同样，对于数据库的表而言，索引就是目录。

对于一个数据库索引来说，一个好的索引构造实现一次查问须要有以下长处：

  • 尽可能少的磁盘 I/O 操作
  • 高效地查问，能够反对范畴查问

为什么呢？

因为索引是保留到磁盘上的，当通过索引查找数据时，就须要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，而后读入到内存，也就是说查问过程中会产生屡次磁盘 I/O，而磁盘 I/O 次数越多，所耗费的工夫也就越大。所以，咱们心愿尽可能少的磁盘 I/O。

另外mysql 是反对范畴查问的，所以也须要一个高效的范畴查问。

那当初咱们尝试看看哪一个索引构造能够满足这些需要。

🧩数组

咱们最开始接触的数据结构就是数组。如果咱们用有序数组来贮存索引，看看后果如何。

为什么抉择是有序呢？因为咱们能够用二分查找在有序数组中疾速地找出指标索引，工夫复杂度能够降落到 O（logn）。

二分查找法每次都把查问的范畴减半, 工夫复杂度也不算高。仿佛看起来是一个不错的抉择。

然而插入新元素的时候性能太低

想想看这么一个例子，咱们有几十万条数据，在两头某个地位插入一个元素，为了让数组放弃有序，须要将这个元素之后的所有元素后移一位。

如果这个操作产生在磁盘中，这必然是灾难性的。因为磁盘的速度比内存慢几十万倍，所以咱们不能用一种线性构造将磁盘排序。

这样揭示了数组的一个特点：查问快而增删慢。

所以，有序数组索引只实用于动态存储引擎，比方你要保留的是 2020 年某个城市的所有人口信息，这类不会再批改的数据。

🌲二叉树

有一种人造适宜二分查找的数据结构，那就是二叉树。

把所有二分查找中用到的所有两头节点，把他们用指针连起来，并将最两头的节点作为根节点,
那么就 取得了一个二叉查找树。

二叉查找树的特点是 一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点。

它能够解决了插入新节点的问题

二叉树不会像线性构造那样插入一个元素，所有元素都须要向后排列。

因而，二叉查找树解决了间断构造插入新元素开销很大的问题，同时又放弃着人造的二分构造。

然而又带来了新的问题：在极其状况下，二叉查找树会进化成链表。

因为每次插入的值，都比节点的值要大. 查问的工夫复杂度进化为 O（n）

因为树是存储在磁盘中的，拜访每个节点，都可能会拜访一个新的数据块，所以树的高度越高，就会影响查问性能。

为了解决这种状况，均衡二叉查找树（AVL 树）🌲 诞生了。

它的特点是：每个节点的左子树和右子树的高度差不能超过 1

插入示例如下，能够看到它会维持自均衡.

然而均衡二叉树还是解决不了，因树变高而影响查问效率的问题。

能够设想一下一棵 100 万节点的均衡二叉树，树高 20。一次查问可能须要拜访 20 个数据块。

在机械硬盘时代，从磁盘随机读一个数据块大略可能须要 10 ms 左右的寻址工夫。也就是说，对于一个 100 万行的表，如果应用二叉树来存储，独自拜访一个行可能须要 20 个 10 ms 的工夫，这个查问可慢到家了。

为了让一个查问尽量少地读磁盘，就必须让查问过程拜访尽量少的数据块 。那么， 咱们就不应该应用二叉树，而是要应用“N 叉”树。

B/B+ 树 🎄

B 树

B 树的每一个节点最多能够包含 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。

一棵 3 阶的 B 树的查问 节点值为 9 的过程:

  1. 与根节点的索引(4，8）进行比拟，9 大于 8，往右边走；
  2. 到节点索引为（10，12），9 小于 10，往左边走；
  3. 找到了索引值 9 的节点

树高 3，最多会产生 3 次磁盘 I/O 操作。

而雷同的节点数量，均衡二叉树的树高更大，拜访 I / O 次数也更多.

在 mysql 的 InnoDB 引擎中，表都是依据主键程序以索引的模式寄存的，这种存储形式的表称为索引组织表。

如果用 B 树作为索引，构造如下：

  • 图中的 p 节点为指向子节点的指针，
  • 图中的每个节点称为页，页就是咱们下面说的磁盘块，在 mysql 中数据读取的根本单位都是页

如果咱们要查找 id=28 的用户信息，那么咱们在上图 B 树中查找的流程如下：

  1. 先找到根节点也就是页 1，判断 28 在键值 17 和 35 之间，咱们那么咱们依据页 1 中的指针 p2 找到页 3。
  2. 将 28 和页 3 中的键值相比拟，28 在 26 和 30 之间，咱们依据页 3 中的指针 p2 找到页 8。
  3. 将 28 和页 8 中的键值相比拟，发现有匹配的键值 28，键值 28 对应的用户信息为(28,bv)。

然而这个数据结构存在什么问题呢？

B 树的每个节点都蕴含数据（索引 + 记录）。

比方咱们要拜访 id 为 28 的用户, 在咱们查问过程中，拜访门路上的数据会从磁盘加载到内存 ，比方咱们要拜访页 3 的索引数据来和 28 做比照，这时候页 3 的数据会全副加载到内存(读取的单位是页), 然而这些记录数据是没用的，咱们只是想读取这些节点的索引数据来做比拟查问。

当用户的记录数据的大小远远超过了索引数据的大小时，这种数据无疑是一种累赘。

B+ 树

B+ 树就是对 B 树做了一个降级，MySQL 中索引的数据结构就是采纳了 B+ 树，B+ 树结构如下图：

和 B 树区别如下：

  • 叶子节点才会寄存理论数据，非叶子节点只会寄存索引；
  • 所有索引都会在叶子节点呈现，叶子节点之间形成一个有序链表

长处如下：

  • 非叶节点不再须要寄存理论数据，能够寄存更多索引，子节点数能够更多，即更加“矮胖”，缩小 I/ O 次数
  • 所有叶子节点间还有一个链表进行连贯，不便了范畴查找。比方查找 12 月 1 日和 12 月 12 日之间的订单，这个时候能够先查找到 12 月 1 日所在的叶子节点，而后利用链表向右遍历，直到找到 12 月 12 日的节点

实际上 innoDB 的 b + 树做了一些改变：

  • 叶子节点之间是用「双向链表」进行连贯，既能向右遍历，也能向左遍历。
  • B+ 树点节点内容是数据页，数据页里寄存了用户的记录以及各种信息，每个数据页默认大小是 16 KB。

综上所述，B+ 树 成为了 MySQL 默认的存储引擎 InnoDB 作为索引的数据结构

聚簇索引 和 二级索引

上面来理解一些概念

每一个索引在 InnoDB 外面对应一棵 B + 树。

假如，咱们有一个 主键列为 ID的表，表中有字段 k，并且在 k 上有索引。并插入了几个值.

这个表的建表语句是：

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

产生的两个 B+ 树如下：

索引类型分为主键索引和非主键索引。右边的树就是主键索引

  • 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引
  • 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索

那么基于主键索引和一般索引的查问有什么区别？

比方 select * from T where ID=300，即主键查问形式，则只须要搜寻 ID 这棵 B + 树, 这很简略

但如果语句是 select * from T where k=3，即一般索引查问形式, 执行流程是什么呢？

  1. 在 k 索引树上找到 k = 3 的记录，获得 ID = 300；
  2. 再到 ID 索引树查到 ID=300 对应的 R3；

也就是说，基于非主键索引的查问须要多扫描一棵索引树。该过程称为 回表

索引优化

笼罩索引

如果执行的语句是 select ID from T where k between 3 and 5，这时只须要查 ID 的值，而 ID 的值曾经在 k 索引树上了，因而能够间接提供查问后果，不须要回表。也就是说，在这个查问外面，索引 k 曾经“笼罩了”咱们的查问需要，咱们称为笼罩索引。

因为笼罩索引能够缩小树的搜寻次数，显著晋升查问性能，所以应用笼罩索引是一个罕用的性能优化伎俩。

最左前缀准则

如果你要查的是所有名字第一个字是“张”的人，你的 SQL 语句的条件是 ”where name like‘张 %’”。这时，你也可能用上这个索引，查找到第一个符合条件的记录是 ID3，而后向后遍历，直到不满足条件为止。

能够看到，不只是索引的全副定义，只有满足最左前缀，就能够利用索引来减速检索。

参考资料：
https://cloud.tencent.com/developer/article/1543335
https://www.xiaolincoding.com/mysql/index/why_index_chose_bpu…
https://funnylog.gitee.io/mysql45/

退出移动版