这篇文章上次修改于 1459 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
MySQL 的基本数据结构
在我们日常开发中，数据库大家肯定并不陌生，数据库底层的数据结构是什么呢？今天我们来揭秘一下。
首先不了解数据库的功能和用途直接谈底层的实现，那无疑是耍流氓。我们先确定一下何为数据库，数据库就是存储数据的一个系统。那么数据库的基本能力是什么呢？其实就是存储数据后，再进行查询数据。OK、现在我们知道了具体需求，那么我们就想一想脑袋中的适用与查询的数据结构。哈希表，树结构，图结构。
然后 哈希表，树，图 该怎么选呢？我们还是要从需求出发，如果你想要高效的缓存数据库那么把哈希表放在内存里直接查询的方式无疑是最快的。如果你想大量并高效的查询关联数据，那么图结构无疑是最高效的。那么我们这片文章选题是 Mysql 的基本数据结构，我们就主要分析一下 Mysql 的数据结构选型。
Mysql 数据结构选型
Mysql 主要还是以表的形式来存储数据的，那么他底层就可以使用 链表，哈希表，树等多种数据类型，然后 Mysql 有个很重要的功能就是查询符合条件的数据然后取后边多少条数据这样的操作。那么哈希表肯定是不好胜任这个工作了。链表倒是可以但是没有树结构效率高（其实我觉得树就是一种特殊的链表）。那么大家肯定听说过二叉查找树。
二叉查找树
但是二叉树效率是挺高，但是还有优化的空间。比如说 Mysql 经常会有条件筛选，那么我们不可能一个节点一个节点的在硬盘中读取到内存中做比较，因为在硬盘读取数据这个效率太差了，就算通过逻辑去控制节点加载也是不行的。1. 两个节点数据在硬盘上不一定是连续的，这样还是会读取多次硬盘。2. 这个加载读取逻辑太复杂了，不利于后期维护和优化。
B 树
那怎么办，有人提出了 B 树，我这里为了画图方便每个节点里面只放了两个元素，实际上会有很多。感兴趣的自己了解一下。这样每次就可以读取一个叶子结点，叶子结点中包含大量连续的数据，然后再内存中做处理就会快很多。那么 B 树有什么问题呢，因为他每个叶子节点里面都包含数据，并且数据使用还不频繁，这就导致每次加载到内存的数据中，有很多无用数据。所以 Mysql 最终选型是 B+ 树。
B+ 树
B+ 树其实就是在 B 树的基础上精简了中间叶子节点的数据。只存放关键数据。我们现在使用最广泛的 Mysql 数据引擎 InnoDB 就是基于 B+ 树实现存储和查询的。
当然 InnoDB 为了更有效率地查询，插入、更新和删除，还做了很多优化，比如每个叶子节点存储数据量的最大值就是磁盘的一个扇区。以及每个叶子节点的空间该怎么利用等一系列优化手段。
扇区：磁盘的最小单位。根据操作系统的不同一般为 4k。
其实链表中还有一种与 B+ 树类似可以适用于 InnoDB 引擎的数据结构「跳表」，但是至于 InnoDB 使用了 B+ 树而没有使用跳表，那就无从得知了。
总结
实际上每种选择的背后，都有大量根据业务、功能实现、性能的考量。没有万能数据结构，只有最合适的。同时以上思路可以借鉴到生活中。
没有评论