MySQL 篇-深入了解索引的内部结构（哈希表、红黑树与 B+ 树）-Toy模板网

这篇具有很好参考价值的文章主要介绍了MySQL 篇-深入了解索引的内部结构（哈希表、红黑树与 B+ 树）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🔥博客主页：【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍

MySQL 篇-深入了解索引的内部结构（哈希表、红黑树与 B+ 树）,MySQL 篇,mysql,数据库,数据结构,链表,哈希算法

文章目录

1.0 索引概述

2.0 索引内部结构特点

2.1 那么哪些数据结构，能够加快查询速度呢？

2.2 二叉搜索树、AVL 树存储结构特点

2.3 红黑树存储结构特点

2.4 哈希表的存储结构特点

2.5 B 树的存储结构特点

2.6 B+ 树的存储结构特点

2.6.1 B+ 树的优势

2.6.2 创建主键索引、创建非主键索引、无索引三种具体的搜索方式

1.0 索引概述

在数据库中，索引是一种数据结构，用于加快对表中数据的检索速度。索引可以类比于书籍的目录，它提供了一种快速查找数据的方法，避免了全表扫描的低效率。

常见的索引操作：查看表中的索引、在表中的某一列创建索引、删除表中的某一列索引。

代码如下：

-- 查看索引
show index from 表名;

-- 在表中的某一列创建索引
create index 索引名 on 表名(列名);

-- 删除表中的某一列索引
drop index 索引名 on 表名;

如何给一个已经包含大量数据的表添加索引？

部署新的数据库，用新的数据库代替旧的数据库。

2.0 索引内部结构特点

索引，一定是引入了一些额外的数据结构，来增加查询的速度。默认情况下，进行条件查询擦欧总，就是遍历表，一条一条数据都带入条件中进行筛选符合的数据。引入索引，就是要通过其他的数据结构，加快查询的速度，减少遍历表的可能性。

2.1 那么哪些数据结构，能够加快查询速度呢？

1）顺序表：随机访问，不能加快查询速度。

2）链表：遍历查询，也不能加快查询速度。

2.2 二叉搜索树、AVL 树存储结构特点

二叉搜索树是可以加快查询速度的，但是分成两种情况：在极端情况，普通的二叉搜索树，最坏就变成了链表，时间复杂度为 O(n) ；如果是一个比较平衡的树，时间复杂度为 O(log N) 。

AVL 树，是一个平衡二叉搜索树，比普通的二叉搜索树解决了变成链表的最坏情况。此时查询就能够做到时间复杂度为 O(log N) 。

2.3 红黑树存储结构特点

红黑树，由于 AVL 树是一个非常严格的的平衡二叉搜索树，随便进行一些增删改查操作，都可能会破坏要求，从而触发旋转，每一次旋转，都是有开销的。而对于红黑树，本质上是一个没有那么严格的平衡二叉搜索树(要求更宽松)，AVL 树任意一个节点，左右子树高度差不能超过 1 ，一旦超过高度差超过 1 就会旋转。所以红黑树触发旋转的概率要远远低于 AVL 树，虽然没有 AVL 树那么平衡，但是查询的时候速度也没差多少。

红黑树里面的元素是有序的，可以进行范围查询。中序遍历就可以进行范围查询。但是由于类似找后继元素这些操作，也未必就高效，很有可能需要让父节点上一系列回溯，才能找到后继。

红黑树的缺点：红黑树是二叉搜索树，当元素非常多的时候，就会使树的高度变得比较高，树的高度越高，进行查询的效率就底。高度每增加一层，比较次数就会增加 1 。数据库的数据/索引都是保存在硬盘上的，上述的每次比较，就需要一次硬盘 IO 操作了。

因此，红黑树不太适合大规模在硬盘上管理数据的场景。

2.4 哈希表的存储结构特点

哈希表的结构是由数组、链表、哈希函数所组成的，哈希函数将键映射到数组的特定位置，即计算出键对应的桶的索引。在哈希表中，可能存在哈希冲突，即不同的键经过哈希函数计算得到相同的桶索引。为了解决这个问题，通常会在每个桶中使用链表或其他解决冲突的方法来存储冲突的键值对。

哈希表通过哈希函数将键映射到存储桶中，使得查找操作的时间复杂度接近 O(1)。这使得哈希表在查找元素时非常高效。

因此，哈希表可以提高查询效率，但是由于特殊的存储结构，存储的数据是随机的，不能通过范围查询得到相应的结果。所以哈希表不适合出现在查询范围数据的场景中。

除此之外，有关于哈希表的时间复杂度的谈论：谈到哈希表的时间复杂度的时候，往往不是谈最坏的情况，就认为是 O(1) ，理由：在这个哈希表中，所有的数据加起来是 n，链表的长度当然不是 n，虽然理论上是存在所有数据都出现在同一个链表中的极端情况。这个情况认为工程上不会存在，除非故意构造一个特别特殊的 hash 函数。当链表最大长度为 m ，复杂度为 O(m) 。由于 m << n，并且选择合适的 hash 函数，就可以确保每一个链表上的元素都不是很多，近似认为 O(1) 了。

2.5 B 树的存储结构特点

以上就是 B 树的大致结构图，为了解决红黑的缺点，降低树的高度，因此 B 树被 “发掘” 出来了，B 树是一种多路搜索树，每个节点可以有多个子节点。相比于二叉搜索树，B树的节点拥有更多的子节点，可以容纳更多的键值对。因此就可以轻松的解决红黑树当元素太多的时候，树的高度高的情况了。

B 树的平衡性：B 树保持平衡，即所有叶子节点都在相同的深度上。这样可以确保在进行查找、插入和删除操作时，各个节点之间的高度差不会过大，保持了较为稳定的查询性能。

B 树的非叶子节点即存在多个值(数据库的理解：每一个值代表一行数据)，也存在多个指针，至于个数的多少，由自己定义。

因此，B 树是一种高效的数据结构，适合用于需要支持范围查询、插入和删除操作的场景。

2.6 B+ 树的存储结构特点

B+ 树的结构图：

B+ 树是 B 树的升级版本，B+ 树也是 N 叉搜索树。

与 B 树不同的是，每个节点都有多个子节点即多个值，每个节点都会含有最大值，如 8 与 15 中，15 就是最大值，那么以下的节点都不能比 15 更大的值出现。每个值都会重复出现，在子节点中都会出现，直到叶子节点中。那么最终值都会出现在叶子节点中，此时叶子节点这一层，就包含了整个数据集合的全集；

还有与 B 树不同的是，所有的非叶子节点中只会存储值，而不是行(用数据库的角度来想这个 “行” 的意思)。在叶子节点中，都是存储的是值与该行的数据 data 。而 B 树的非叶子节点、叶子节点都会存储对应的行(一个值对应一行数据)。

因此，当查找值为 8 的数据行时，不单单只找到包含 8 的节点，需要从上往下找到叶子节点处，因为叶子节点存储的是该行的数据，而非叶子节点存储的是值(数据库中的列,如 id 这列的数据)。因此，查询是非常稳定的，时间复杂度为 O(logₘ n)，其中 m 为每个节点的最大子节点数，n 为总的数据量。

与 B 树不同的是，最后这一层，即非叶子节点之间都是通过链表来相连接，以便范围查询等。

2.6.1 B+ 树的优势

1）非常方便进行遍历和范围查询。

2）当前任何一次查询操作，最终都是要落到叶子节点完成。查询任何数据，经历的硬盘 IO 操作次数都是一样的，稳定性好。

3）由于叶子节点，是数据的全集，对应的，非叶子节点中，都是重复出现的数据，就可以把表每一行的数据，最终都关联到叶子节点这一层，非叶子节点中值保存一个单纯的 Key 值即可(id)，且非叶子节点可以在内存中缓存。

例如：使用 id 这一列来做为索引，这里 B+ 树的非叶子节点，都只需要保存一个 id 这样的值就行了。到叶子节点这里，每个叶子节点不光要保存 id 还要把后续的 name 、classid 等信息也要保存起来。

补充：实际上，在 innodb 存储引擎中底层的数据结构就是 B+ 树的结构，就会按照主键的索引的 B+ 树的叶子节点来保存每一行的数据。如果表中已经创建了主键，自然是通过已经创建的主键索引的 B+ 树来组织所有行；如果没有创建主键，MySQL 其实生成了一个隐藏的主键，按照隐藏主键构造的 B+ 树来组织行。

2.6.2 创建主键索引、创建非主键索引、无索引三种具体的搜索方式

1）表中存在主键索引，比如在 id 列中创建了主键索引，那么就会按照 B+ 树的结构从上往下进行搜索，在叶子节点中找到相对应的行。

2）表中没有手动创建主键索引时，MySQL 会自动创建隐藏主键来帮助组织数据。创建了非主键索引时，根据非主键索引的 B+ 树进行搜索，有一点需要重点注意：非主键创建的索引中，叶子节点保存的时主键的值，比如 id ，而不是存储整个数据，非叶子节点是存储相对应的值(根据非主键索引创建 B+ 树的值)，这是另外的一个 B+ 树，与隐藏主键创建的 B+ 树不是同一个。接着，找到了相对应的 id 后，会来到由隐藏主键创建的 B+ 树中搜索，这个 B+ 树的叶子节点存储的就是整个数据，数据的集合。通过走完两个不同的 B+ 树后，就可以得到相对应的行了。简单来说，不管是否手动创建主键索引，只要是通过非主键索引来搜索数据，都是需要各走一次不同的 B+ 树。

3）不通过索引来搜索数据。这个较为简单，既然该列中没有索引，那么只能全盘搜索，通过叶子节点的链表来搜索数据。查询的速度比不上根据索引查询的快。

MySQL 篇-深入了解索引的内部结构（哈希表、红黑树与 B+ 树）,MySQL 篇,mysql,数据库,数据结构,链表,哈希算法文章来源地址https://www.toymoban.com/news/detail-839735.html