本篇文章给大家带来了关于mysql的相关知识，其中主要介绍了关于索引结构的相关问题，那么，索引的结构是什么样的？为什么索引可以这么快？下面一起来看一下吧，希望对大家有帮助。
程序员必备接口测试调试工具：立即使用
Apipost = Postman + Swagger + Mock + Jmeter
Api设计、调试、文档、自动化测试工具
后端、前端、测试，同时在线协作，内容实时同步
推荐学习：mysql教程
数据库存储单位
首先我们要知道，由于为了实现持久化，只能将索引存储在硬盘上，通过索引来进行查询的时候就会产生硬盘的 I/O 操作，因此，设计索引时需要尽可能的减少查找次数，从而减少 I/O 耗时。
此外还需要知道一个很重要的原理：数据库管理存储空间的基本单位是页(Page)，一个页中存储多条行记录(Row)。
计算机系统对磁盘 I/O 会做预读优化，当一次I/O时，除了当前磁盘地址的数据以外，还会把相邻的数据也读取到内存缓冲池中，每一次 I/O 读取的数据成为一页，InnoDB 默认的页大小是 16KB。
连续的 64 个页组成一个区(Extent)，一个或多个区组成一个段(Segment)，一个或多个段组成表空间(Tablespace)。InnoDB 有两种表空间类型，共享表空间表示多张表共享一个表空间，独立表空间表示每张表的数据和索引全部存在独立的表空间中。
数据页结构如下（图源：极客时间《MySQL 必知必会》）：
数据页的 7 个结构内容可以大致分为以下三类：
- 文件通用部分，用于校验页传输完整
- 文件头（File Header）: 表述页信息，文件头中使用 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 构成一个双向链表，分别指向前后的数据页。
- 页头（File Header）：记录页的状态信息
- 文件尾（File Trailer）: 校验页是否完整
- 记录部分，用于存储数据记录
- 最大最小记录（Infimum/Supremum）：虚拟的行记录，表示数据页的最大记录和最小记录。
- 用户记录（User Record）和空闲空间（Free Space）: 用于存储数据行记录内容
- 索引部分，用于提高记录的检索效率
- 页目录（Page Directory）：存储用户记录的相对位置
详情可参考淘宝的数据库内核月报
索引数据结构
很自然的，我们会想到查找算法中涉及到的一些常用数据结构，比如二叉查找树，二叉平衡树等等，实际上，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, 表示每个节点最多能有多少个子节点)，
- 每个磁盘块中最多包含
k - 1个关键字 和k个子节点的指针 - 叶子节点中，只有关键字，没有子节点指针
- 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
- 所有叶子节点位于同一层。
上面已经提到，每一次 I/O 会预读一个磁盘块的数据，大小为一页，用一个磁盘块的内容表示一次 I/O，B 树的结构如下图 (图源：极客时间 SQL 必知必会)：
B 树也是有序的，由于子节点指针一定比关键字多 1，所以正好可以用关键字划分子节点的区段，如图中的例子，每个节点有 2 个关键字，3 个子节点，如磁盘块 2 ，第一个字节点的关键字 3，5 小于自身的第一个子节点 8，第二个子节点的 9，10 在 8 和 12 之间，第三个子节点的值 13，15 大于自身的第二个子节点 12。
假设我们现在要查找 9，步骤如下：
- 与根节点磁盘块 1 (17,35) 比较，小于 17，继续在指针 P1 中查找，对应磁盘块 2
- 与磁盘块 2 (8,12) 比较，位于两者之间，继续在指针 P2 查找，对应磁盘块 6
- 与磁盘块 6 (9, 10) 比较，找到 9
可以看到，虽然做了很多次比较的操作，但是由于进行了预读，所以在磁盘块内部的比较是在内存中进行的，不耗费磁盘 I/O，上述操作只需要进行 3 次 I/O 即可完成，已经是比较理想的结构了。
B+ 树索引
B+ 树在 B 树的基础上进行了进一步的改进，B+ 树和 B 树的区别有以下几点：
- B+ 树的构建方式是，对于父节点中的关键字，左子树的所有关键字小于它，右子树的所有关键字都大于等于它
- 非叶子节点仅用于索引，不会存储数据记录
- 父节点的关键字也会出现在子节点中，并且都是子节点中的最大值（或者最小值）
- 所有关键字都会出现在叶子节点中，叶子节点构成一个有序链表，按从小到大排序。
示例如下，本例中，父节点的关键字都是子节点中的最小值 (图源：极客时间 SQL 必知必会)：
假设要查找关键字 16，查找步骤如下：
- 与根节点磁盘 1 (1,18,35) 比较，16 在 1 和 18 之间，得到指针 P1，指向磁盘 2
- 找到磁盘 2 (1,8,14)，16 大于 14，得到指针P3，指向磁盘 7
- 找到磁盘 7 (14,16,17)，找到16
B+ 树优点：
- 内部节点不存储数据，因此每个内部节点可以存储的记录数量远大于 B树，树的高度更低，I/O 更少，每次 I/O 读取的数据页里内容更多
- 可以支持范围查询，直接在叶子节点组成的有序链表遍历即可
- 所有数据都存储在叶子节点，因此查询效率更稳定
HASH 索引
MySQL 的 memory 存储引擎默认的索引结构是 Hash 索引，Hash 是一种函数， 称为散列函数，通过特定算法（如 MD5, SHA1，SHA2 等）将任意长度的输入转换为固定长度的输出，输入和输出一一对应，本文不会对 hash 函数做深入的介绍，详情请参考 百度百科。
Hash 查找的效率为 O(1)，效率非常高，python 的 dict，golang 中的 map，java 中的 hash map 都是基于 hash 实现的，在 Redis 这样的 Key-Value 数据库也是由 Hash 实现。
对于精确查找而言，Hash 索引的效率会比 B+ 树索引更高，但是 Hash 索引有一些局限性，因此不是最主流的索引结构。
- 因为 Hash 索引指向的数据是无序的，所以Hash 索引不能范围查询，也不支持 ORDER BY 排序。
- 由于 Hash 是精确匹配，因此也不能进行模糊查询。
- Hash 索引不支持联合索引的最左匹配原则，联合索引只有在完全匹配时生效。因为 Hash 索引计算 Hash 值的时候是将索引合并后再一起计算 Hash 值，而不会计算每个索引的单独 Hash 值。
- 如果被索引字段的重复值很多，那就会造成大量的 Hash 冲突，这时候查询就会变得非常耗时。
基于上述原因考虑，Mysql InnoDB 引擎不支持 Hash 索引，但是在内存结构中有一个自适应 Hash 索引的功能，当某个索引值使用非常频繁的时候，会在 B+ 树索引的基础上自动创建一个 Hash 索引，来提高查询性能。
自适应 Hash 索引可以理解为一种 “索引的索引”，采用 Hash 索引储存 B+ 树索引中的页面地址，迅速定位到对应的叶子节点。可以通过 innodb_adaptive_hash_index 变量来查看。
推荐学习：mysql教程
以上就是深入了解MySQL索引结构的详细内容，更多请关注php中文网其它相关文章！
声明：本文转载于：CSDN，如有侵犯，请联系admin@php.cn删除
程序员必备接口测试调试工具：点击使用
