乐趣区

关于mysql:mysql-索引

为什么 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/

退出移动版