前言
昨天有一个女孩问我有没有什么立竿见影的方法可以提高数据库查询性能？
这只是一个评分问题。 我得意又略带不屑地说，当然，我加了一个“索引”。
她不紧不慢地问为什么建立索引可以提高查询性能。
不用问，索引就像一本书的目录，利用目录来检索当然是非常快的。
她失望地摇摇头。 你说的只是类比，但是为什么通过目录可以提高查询速度呢？
哦，是的，你可以通过参考书目快速搜索。 这只是一个现象。 真正的原因是什么？
女孩用惊讶而僵硬的表情看着我，满意而意味深长地笑了：原来你这个男程序员不知道该怎么做。 看来我得自己研究一下了。
唉，熬夜会让我这该死的美人又显得憔悴了。
来自同辈的羞辱是可以忍受的还是不能忍受的？ ！
于是，我踏上了学习数据库索引的不归路。 事实证明，数据库索引使用了一种古老的数据结构，称为 B+ 树。 当然还有Hash等其他类型。 暂且不说，但是B+树到底是个什么怪物呢？
让我们简单回顾一下这棵树的前世今生。
文本二叉树
具有层次关系的集合是由n（n>0）个有限节点组成的，看起来像一棵倒立的树，所以这样的数据结构称为树。
一个节点的子节点数量称为度，通俗地说就是树的分叉数量。 树中最大的度称为树的度，也称为阶。 二阶树最多有2个子节点，即最多有2个分叉，所以这样的树称为二叉树。 二叉树是树族中最简单的树。
有两个分叉的树是二叉树，但除了用于以某种结构存储数据之外，它似乎与查询性能没有任何关系。 这不就是又一个无用的噱头吗？
二分查找
我听说二叉树最初的威力来自于一种叫做二分搜索的算法。
相传，在鹦鹉的原始社会，有严格的等级制度，每只鸟都必须按照身高和尊严的顺序排列。
那么问题来了，如下图所示，我们如何找到最高的、最矮的、中高的、以及指定高度的鹦鹉呢？
第一种方法：扫描法
一一测量，完成后一切问题就迎刃而解了。
这种一一测量的方法称为扫描。 其缺点是显而易见的。 在所有测量完成之前，无法得知最高和最矮的值。
对于指定的高度，最好的情况是第一次就找到了； 最坏的情况是最后一次找到，时间复杂度为n。 也就是说，在13只鹦鹉中找出符合指定高度的一只。 最坏的情况就是最后一次找到它。 这种情况要检查13次。
第二种方法：二分法
13只鹦鹉全部听从命令，从矮到高排成一排，向左看，数数。
数字1是最矮的，数字13是最高的，数字7是中等高度的。
立即发现最好和最坏的情况。 查询性能一下子提升了13倍。 亲爱的，无论有多少只鹦鹉，时间复杂度都是1，这太可怕了。
问：我不相信。 你正试图改变这个概念。 您可以比较鹦鹉搜索指定高度的表现。
因为鹦鹉是按照高度排列的，所以指定高度的鹦鹉要么是站在中间的，要么是在其左侧或右侧的一组。
如果是中间的，一口气找到。 如果不是，只需从中间的左半边或右半边找到，然后在这半边找到中间的，比较高度即可。
以此类推，每次查询范围减半，时间复杂度为log2(n)。
那么log2(13)就是4，最坏的情况也只有4次。 时间复杂度确实不是1，但是看起来也不错。 简化如下：
问题：如果按高度排队，还是需要一一比较。 它和扫描有什么区别？ 为什么不直接扫描呢？
情况确实如此。 简单的查询，先排序再二分查找，不一定比扫描快，甚至更差。
然而，在数据的世界中，大多数数据在一生中都会被查询无数次。 如果数据诞生时只排序一次，那么余生都可以直接使用二分查找。 这似乎就是传说中的多读少写。 ，以及相应的重用。
优势：
缺点：
二叉搜索树
如果一组数据不改变或者不经常改变，那么它们的位置将基本保持不变。 然而，每次查询都重新计算中间位置是一种浪费，而且是一种可耻的浪费。
我们能不能把所有的中间节点组织起来，每次使用的时候都直接去取呢？
请看下图，找到一次二分查找的所有中间节点，将它们连接起来，用手抬起中间节点，它就是一棵二叉查找树。
优点：二叉搜索树通过数据结构实现二分搜索算法。 通过存储中间节点的数据，弥补了二分查找每次都要计算中间位置的缺点。
平衡二叉树：
如果二叉搜索树不断被修改，比如删除某些节点，一段时间后，最早的中间节点的数据（根）很可能不再在中间了。
中间的位置就像天平的支点。 如果不再处于中间，整个尺度就会不平衡，不平衡的世界就会塌陷成一棵不伦不类的跛脚树，甚至降维成链表或数组。
二分查找算法的关键在于排序和中间节点，而二分查找树的关键在于中间节点的维护。 如果所维护的节点不再位于中间，那么它就失去了意义。
因此，我们必须保证“二叉搜索树”是一棵正确的树，是根节点在中心的树，是左右子树层次（高度）基本相等（高度差不超过1）的树，以及一棵平衡树。
最常见的平衡二叉树是红黑树：
红黑树规定了一系列节点颜色规则，以及相应的左转和右转操作，以保证颜色规则，实现树的平衡。
看到这些花哨的颜色和复杂的规则让人一看就望而却步，但这一切都只是为了保证二叉树的平衡。 因为维持平衡的操作实在是太麻烦了，不是一句话就能概括的。 我们必须用一堆与人鬼无异的规则和步骤来实现它。 只要按照这几个步骤，一定能够实现二叉树的平衡。
平衡二叉树=二叉查找树+平衡（左右高度差不超过1）
平衡二叉树并不能提高二叉搜索树的性能。 它只是保证正树不会受到双向陪衬（多次增删改查）的影响而成为链表或者非对称不完全树，并且永远保持平衡。
另外，不只是二叉树，其他类型的树也需要有序和平衡，才能发挥出最大的威力。
多树的B树
有两个分叉的树可以将查询减半，理论上可以使性能加倍。 那么，多个分叉是否可以将性能提升更多倍呢？
三阶（分叉）树如下图（所有数据仅供演示，并非真实分布）
每个节点维护两条数据，最多指向3个子节点。 如图3所示，子节点的数据为：小于17、17~35、大于35。
假设，要从上图中找出数字10，步骤如下：
找到根节点，比较10、17、35的大小，发现10 < 17在左子节点，即第二层节点；
从根节点的指针开始，找到左子节点，将10与8、12的大小进行比较，发现8 < 10 < 12，数据在当前节点的中间子节点，即第三个层节点；
通过上一个节点的指针，找到中间子节点（第三层节点），将10与9、10的大小进行比较，发现9 < 10 == 10，所以找到当前节点的第二个数为结果。
将忽略的 12 个数据相加，从 26 个数据中查找数字 10 仅需要 log3(26)≈ 3 次。 如果使用平衡二叉树，则需要log2(26)≈5倍。 事实证明，多叉树确实再次提高了查找性能。
多树是在二叉搜索树的基础上，增加单个节点的数据存储数量，同时增加树的子节点数量。 一次计算可以进一步缩小搜索范围。
优点：基于二叉平衡树，一次加载节点就可以加载更多的路径数据，同时将查询范围缩小到更小的规模。
复杂节点：
到目前为止，我们列出的数据都是单个数字。 试想一下，你手里已经有一个数据数字10了，为什么还要费尽心思从一堆数据中找出这个10，并且自己去找呢？ 这不是病吗？
单个数字只能存在于演示中。 现实世界要复杂得多。 我们来看一个接近真实场景的案例。
现有一棵按年龄索引的三阶树，存储了一批用户信息，如下图：
数字是用户的年龄，其他都是与树排序和搜索无关的业务数据。 这样的索引数据维护在与树排序和搜索无关的业务节点上。 平衡多叉（序）树称为B树（B-tree）。 。
缺点：业务数据的大小可能远远超过索引数据的大小。 每次需要将数据加载到内存和CPU缓存中进行查找和比较计算时，都必须找到所有索引数据和不相关的业务数据。 原本可以一次加载所有索引数据，但现在需要多次加载。 如果比较的节点不是查询的数据，那么加载到内存中的业务数据就没用了，全部丢弃。
磁盘输入/输出
计算机的主要功能是：计算、存储和网络。 很大一部分用于计算的数据和计算结果需要存储以供后续重用。 磁盘存储和读取的过程称为磁盘 I/O。 磁盘的读取方式和速度会严重影响整个业务的计算性能。
让我们简单了解一下磁盘的工作原理。
磁盘大概是这样的：
磁盘主要由盘片、传动臂、读写头和电机等组成。
为了存储容量，主轴将多个磁盘像糖葫芦一样放入阵列中。 电机带动主轴旋转和传动臂移动，从而使读写头在磁盘上读写数据。 大致是这样的：
圆盘由许多不同半径的同心圆组成。 这些圆圈称为磁道，数据写入这些磁道上。
每个磁道被分成称为扇区的块。
如果说磁盘是记事本，那么磁盘就是笔记本的一页，主轴就是笔记本的装订线； 磁道是页面的行，而扇区可以被视为非常宽的列。
如果将一首诗存储在磁盘上，它可能看起来像这样。
磁盘读I/O操作需要找到数据所在的磁盘片，以及对应的磁道和扇区。 这些操作类似于在书中查找数据所在的页、行和列。
因为每个磁盘片对应一个磁头，所以性能的关键在于查找行和列，即寻道和磁盘旋转。 寻道就是通过磁头找到数据所在的磁道，相当于绕到数据所在的线路上。 由于磁头只能水平移动，即只能寻新行，不能在指定磁道上移动，所以磁盘需要高速旋转才能移动到指定扇区，类似于写春联时，笔不动，纸动。
综上所述，磁盘的读写是通过机械运动来定位数据的位置，而CPU则是通过电信号进行数字运算。 粗略地说，机械查询数据的性能与光处理数据的速度不是一个级别的。 总而言之，磁盘处理速度太慢。
虽然磁盘处理数据太慢，但它是目前相对便宜且稳定的存储设备，因此不能丢弃。 但一般可以通过以下方法进行优化。
多树的B+树
作为数据库的索引，无论用什么数据结构来维护，数据最终都会存储在磁盘上。
鉴于磁盘I/O的性能问题以及每次I/O获取数据量的上限，提高索引本身I/O的最好办法就是减少I/O次数并获取每次都有有用的数据。
B树大大提高了树族的性能。 它将多个数据集中存储在一个节点中，这本身就可以减少 I/O 次数或寻道次数。
但还有一个致命的缺陷，那就是它的索引数据是和业务绑定的，而业务数据的大小很可能远远超过索引数据，这会大大减少一次I/O中有用数据的获取。 间接增加I/O数量以获得有用的索引数据。
因为业务数据是我们查询的最终目标，但在“二分”搜索过程中却是无用的数据。 那么，我们只将业务数据存储在最终查询到的节点中可以吗？
理想很丰满，现实却很骨感。 谁知道到底要查询的节点是哪个节点呢？
B+树诞生了。 B+tree是一种平衡多树，将索引数据和业务数据进行拆分。
B+树中，非叶子节点只存储索引数据，叶子节点存储索引数据和业务数据。 这样保证了叶子节点简单干净，数据量大大减少，最终能找到对应的业务号。 不仅提高了单次I/O数据的有效性，减少了I/O次数，还实现了业务。
但是，索引与数据中的数据是分开的，与示例不同？
如图：我们只需要将真实的业务数据替换为数据所在的地址即可。 此时，业务数据所在的地址就作为B+树中的业务数据。
总结知识拓展
树结构最大的优点是查询性能高，所以任何需要提高查询性能的人都可以考虑树。
现实中确实有这样的例子，比如：
以上只是简单领略了数据库为什么使用B+树索引来提高查询性能的原因和简单过程。
没有详细介绍各种数据结构，也没有提及其他索引类型和索引的具体存储格式。 目的只是为了让大家对指数有一个感性的认识。
最近写了一些有趣的东西，每篇文章都很有思想。 欢迎朋友们阅读/点赞/分享：
我是Guide，一名Java后端开发人员，一点前端知识，一个喜欢做饭的自由男孩。 比主角更正见的技术人。 下次见！
