深入了解MySQL索引结构

本篇文章给大家带来了关于mysql的相关知识，其中主要介绍了关于索引结构的相关问题，那么，索引的结构是什么样的？为什么索引可以这么快？下面一起来看一下吧，希望对大家有帮助

    本篇文章给大家带来了关于mysql的相关知识，其中主要介绍了关于索引结构的相关问题，那么，索引的结构是什么样的？为什么索引可以这么快？下面一起来看一下吧，希望对大家有帮助。<p><img src="https://img.mryunwei.com/uploads/2023/04/20230416183507887.jpg"></p>

推荐学习：mysql教程

数据库存储单位

首先我们要知道，由于为了实现持久化，只能将索引存储在硬盘上，通过索引来进行查询的时候就会产生硬盘的 I/O 操作，因此，设计索引时需要尽可能的减少查找次数，从而减少 I/O 耗时。

此外还需要知道一个很重要的原理：数据库管理存储空间的基本单位是页(Page)，一个页中存储多条行记录(Row)。

计算机系统对磁盘 I/O 会做预读优化，当一次I/O时，除了当前磁盘地址的数据以外，还会把相邻的数据也读取到内存缓冲池中，每一次 I/O 读取的数据成为一页，InnoDB 默认的页大小是 16KB。 连续的 64 个页组成一个区(Extent)，一个或多个区组成一个段(Segment)，一个或多个段组成表空间(Tablespace)。InnoDB 有两种表空间类型，共享表空间表示多张表共享一个表空间，独立表空间表示每张表的数据和索引全部存在独立的表空间中。

数据页结构如下（图源：极客时间《MySQL 必知必会》）： 数据页的 7 个结构内容可以大致分为以下三类：

索引数据结构

很自然的，我们会想到查找算法中涉及到的一些常用数据结构，比如二叉查找树，二叉平衡树等等，实际上，Innodb 的索引是用 B+ 树 来实现的，下面我们来看看为何会选择这种索引结构。

二叉树的局限性

先来简单回顾一下二叉搜索树（Binary Search Tree）的定义，二叉搜索树中，如果要查找的 key 大于根节点，则在右子树中搜索，如果 key 小于根节点，则在左子树中搜索，直到找到 key 为止，时间复杂度为 O(logn)。比如数列 [4,2,6,1,3,5,7]，会生成如下二叉搜索树： 但是在某些特殊情况下，二叉树的深度会非常大，比如 [1,2,3,4,5,6,7]，则会生成如下的树： 在下面这种情况中，最坏的情况下需要查 7 次才能够查到想要的结果，查询时间变成了 O(n)。

为了优化这种情况，就有了平衡二叉搜索树（AVL 树），AVL 树是指左右子树的高度相差不超过 1 的树，搜索时间复杂度为 O(logn)，这已经是比较理想的搜索树了，但是在动辄几千万行记录的数据库中，树的深度还是会很高，依然不是最理想的结构。

B 树

那么，如果从二叉树扩展到 N 叉树呢，很容易想象到，N 叉树可以大大的减少树的深度，实际上，4 层树结构就已经可以支撑几十 T 的数据了。

B 树（Balance Tree）就是这样的一种 N 叉树， B 树也称为 B- 树，满足如下定义： 设 k 为 B 树的度 (degree, 表示每个节点最多能有多少个子节点)，

假设我们现在要查找 9，步骤如下：

B+ 树索引

B+ 树在 B 树的基础上进行了进一步的改进，B+ 树和 B 树的区别有以下几点：