本文转载自微信公众号《小林编码》，作者木叶小小。转载本文请联系小林编码公众号。前言昨天有个妹子问我，什么是立即提高数据库查询性能的最好方法？这只是一个子问题。我得意又略带轻蔑地说，当然是加“索引”了。她不紧不慢地问，为什么索引可以提高查询性能。不用问了，索引就像一本书的目录，用目录来查找当然很快。她失望地摇摇头。你说的只是一个类比，但是为什么可以通过目录来提高查询速度呢。唉，是的，这只是一个现象，你可以通过参考书目快速搜索。真正的原因是什么？女孩用惊讶和僵硬的表情看着我，满意而意味深长地笑了笑：原来你这个男程序员也做不到。看来我得自学了。哎，熬夜又让我这该死的美貌憔悴了。来自同龄人的羞辱，是可忍还是不可忍？！于是，我走上了数据库索引学习的不归路。原来数据库索引使用的是一种古老的数据结构，叫做B+树。当然还有Hash等类型。说吧，不过B+树是个什么怪物？让我们一起来领略一下这棵树的前世今生。一棵字面量二叉树由n(n>0)个有限节点组成一个集合，具有层次关系，看起来像一棵倒置的树，所以这种数据结构称为树。一个节点的子节点的个数称为度，一般为树分叉的个数。一棵树中最大的度称为树的度，也称为阶。一棵二阶树最多有2个子节点，即最多有2个叉子，所以这样的树称为二叉树，二叉树是树族中最简单的树。二叉树是二叉树，但除了用来按照一定的结构存储数据外，似乎与查询性能无关。这不会是另一个无用的噱头。BinarySearch据说二叉树的原始强大来自于一种叫做二分查找的算法。相传，在鹦鹉的原始社会，有严格的等级制度，每只鸟都要按照身高、尊严的先后顺序进行分类。那么问题来了，如下图，我们如何找出最高、最矮、中等身高的鹦鹉，以及指定身高的鹦鹉呢？第一种方法：扫描法逐一测量，完成后全部作答。容易解决。这种一一测量的方法称为扫描，其缺点是显而易见的，最高和最短只有在所有测量完成后才能知道。对于指定的高度，最好的情况是第一次找到；最坏情况是上次找，时间复杂度为n，也就是说从13只鹦鹉中找到指定高度的那个，最坏情况是查13次。方法二：二分法13只鹦鹉全部服从顺序，从低到高排成一列，向左看，报数。1号最矮，13号最高，7号中等身高。一次找到最好和最坏的情况。并且查询性能一下子提升了13倍。我的好孩子，不管有多少只鹦鹉，时间复杂度都是1，太可怕了。问题：我不同意，你在偷换概念，你有能力比较在指定高度搜索一只鹦鹉的性能。因为鹦鹉已经按照高度排好了，指定高度的鹦鹉要么是站在中间的那只，要么是站在它左边或右边的那一组。如果是中间那个，一次性找到。如果不是，只需要从中间的左半边或者右半边找，然后在这一半边找中间的那个，比较高度。以此类推，每次查询的范围减半，时间复??杂度为log2(n)。那么log2(13)就是4，最坏情况只有4次，时间复杂度确实不是1，但是好像还不错，简化如下：问题：如果按高度排队，还是需要比较一个一、这和扫描有什么区别，为什么不直接扫描呢？事实的确如此，简单的查询，先排序，再二分查找，不一定比扫描快，甚至更差。然而，在数据的世界里，大部分数据一生都会被查询无数次。如果你在数据刚出生的时候只对它排序一次，那么你这辈子都可以直接用二分查找。这似乎就是传说中的多读少写，对应的复用。优点：查找速度快缺点：必须提前排序排序每次查找都需要不断计算中间位置二叉查找树如果一组数据不发生变化或者变化不频繁，那么它们的位置基本保持不变。但是，每次查询都需要重新计算中间位置，这是一种浪费，这种浪费是可耻的。能不能把中间节点全部组织起来，每次用到的时候直接拿中间节点呢？请看下图，找到单个二分查找的所有中间节点，将它们连接起来，用手把中间的节点抬起来，就是一棵二叉查找树。优点：二叉查找树通过数据结构实现了二分查找算法。通过存储中间节点的数据，弥补了每次二分查找都要计算中间位置的缺点。平衡二叉树：如果不断修改二叉查找树，比如删除一些节点，经过一段时间后，最早的中间节点的数据（根）可能不在中间。中间位置就像天平的支点。如果不在中间，整个平衡就会失去平衡，不平衡的世界就会坍塌成一棵不伦不类的跛脚树，甚至降维成链表或数组。二分查找算法的关键在于有序节点和中间节点，二叉查找树的关键在于中间节点的维护。如果维护的节点不再在中间，那么它就失去了意义。因此，必须保证“二叉查找树”是一棵正确的树，根节点为中心的树，左右子树层级（高度）基本相等（高度差不超过1）的树)和一棵平衡树。最常见的平衡二叉树是红黑树：红黑树规定了一系列的节点颜色规则，以及相应的左手和右手操作来保证颜色规则，从而达到平衡那个树。看着花哨的颜色和复杂的规则，乍一看让人望而生畏，但这一切都只是为了保证二叉树的平衡。因为保持平衡这个操作太麻烦了，不是一句话可以概括的。它必须通过一堆难以区分的规则和步骤来实现。只要遵循这些步骤，就可以实现二叉树的平衡。平衡二叉树=二叉搜索树+平衡（左右高度差不超过1）平衡二叉树并没有提升二叉搜索树的性能，只是保证树不会被双向箔击中（多次增删改查）降维成链表或不对称的断树，始终保持平衡。此外，不仅是二叉树，其他类型的树也需要有序和平衡才能发挥最大的威力。多叉树的B树的双叉树可以进行半查询，理论上性能可以提高一倍，那么多叉是否可以提高更多倍的性能呢？3阶（fork）树如下图（所有数据仅供demo，不做真实分发）每个节点维护2个数据点，最多指向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次，结果多fork树确实再次提高了查找性能。多叉树是在二叉搜索树的基础上，增加了单个节点的数据存储数量，增加了树的子节点数量。一次计算可以进一步缩小搜索范围。优点：基于二叉平衡树，一次加载节点可以加载更多路径数据，同时将查询范围缩小到更小。复杂节点：到目前为止，我们列出的数据都是孤立的单数。试想一下，你手里已经有了一个数字10，为什么还要费力从一堆数据中找出这个10，自己去找呢？这不是有病吗？单个数字只能活在演示中，真实世界要复杂得多，我们来看一个贴近真实场景的案例。有一个年龄索引的3级树，存储了一批用户信息，如下图：数字是用户的年龄，其他都是业务数据，与树排序无关搜索，这样的索引数据与树排序和搜索无关业务在称为B树（B-tree）的节点上维护平衡的多叉（等级）树。缺点：业务数据的大小可能远远超过索引数据的大小。每次需要将数据加载到内存和CPU缓存中进行查找比对计算时，所有的索引数据和不相关的业务数据都要被检查出来。本来所有的索引数据可以一次加载，现在需要多次加载。如果被比对的节点不是被校验的数据，那么加载到内存中的业务数据就没有用，被丢弃。磁盘I/O计算机的功能主要有：计算、存储和网络。有很大一部分用于计算的数据和计算结果需要存储起来，以便后续再利用。从磁盘存储和读取的过程称为磁盘I/O。磁盘读取的方式和速度会严重影响整个业务的计算性能。让我们简要了解一下磁盘的工作原理。磁盘长这样：磁盘主要由磁盘盘片、传动臂、读写磁头和电机组成。为了存储容量，主轴将多个磁盘片组成一个阵列，就像穿糖葫芦一样。电机带动主轴转动和传动臂移动，使读写头在磁盘上读写数据。大致如下：磁盘盘片由许多不同半径的同心圆组成。这些圆圈称为磁道，数据就写在这些磁道上。每个磁道被分成称为扇区的块。如果磁盘是记事本，那么磁盘就是书的一页，主轴就是书的装订；轨道就是页面的行，扇区可以看作是一个很宽的列。如果你把一首诗存到磁盘上，它在你的想象中会是这个样子。对于磁盘读I/O操作，需要找到数据所在的磁盘片，以及对应的磁道和扇区。这些操作类似于从一本书中查找数据的页、行和列。因为每个磁盘片对应一个磁头，所以性能的关键是找行和列，也就是寻道和磁盘旋转。寻道就是通过磁头找到数据所在的磁道，相当于绕到数据所在的线。由于磁头只能水平移动，即只能寻行，不能在指定磁道上移动，所以磁盘需要高速旋转才能移动到指定扇区，类似于写春联，笔不动，纸动。综上所述，磁盘的读写是通过机械运动来定位数据的位置，而CPU是通过电信号进行数字运算。粗略地说，机械查询数据的性能与光速处理数据的性能不是一个级别的。一句话，磁盘处理太慢了。虽然磁盘处理数据的速度太慢，但它是目前比较便宜且稳定的存储设备，所以不能丢弃，但可以通过以下方法进行优化。尽量减少I/O次数，比如使用缓存；尝试为每个I/O获取更多数据；尝试为每个I/O获取有用的数据，当然相应地间接减少I/O总数；multi-forktree使用B+树作为数据库的索引。不管用什么数据结构来维护，数据最终都会存储在磁盘上。鉴于磁盘I/O的性能问题和每次I/O获取数据量的上限，提高索引本身I/O的最佳方式是减少I/O次数和每次都能获得有用的数据。B树大大提高了树族的性能。它将多个数据存储在一个节点中，这本身可以减少I/O次数或寻道次数。但是还是有一个致命的缺陷，就是它的索引数据是和业务绑定的，业务数据的大小很可能会远远超过索引数据，这会大大减少一个I/O获取有用数据的机会.间接增加I/O的数量以获得有用的索引数据。因为业务数据是我们查询的最终目的，但在“二分”搜索过程中也是无用数据。所以，如果最后查询到的节点只存放业务数据，是不是就可以了？理想很丰满，现实很骨感，谁知道最后要查询的节点是哪个节点呢？B+树是凭空诞生的，B+树是一种平衡的多叉树，用于拆分索引数据和业务数据。在B+树中，非叶子节点只存放索引数据，叶子节点存放索引数据和业务数据。这样既保证了叶子节点的简单干净，大大减少了数据量，又保证了最终能找到对应的业务号。既提高了单次I/O数据的有效性，又减少了I/O次数，实现了业务。但是在数据中，索引和数据是分开的，不像例子？如图：我们只需要将真实的业务数据替换成数据的地址即可。此时业务数据的地址作为业务数据在B+树中。总结数据存储在磁盘上（SSD和CPU性能不在一个数量级），磁盘处理数据很慢；提高磁盘性能主要是通过减少I/O次数和单次I/O有效数据量；通过多阶段索引（一个节点保存多个数据并指向多个子节点）使树结构更加chunky，从而减少I/O次数；索引通过B+树将业务数据与索引数据分离，增加单次I/O的有效数据量，从而减少I/O次数；索引可以通过树数据的排序和“二分搜索”（多阶树可以假设为多点搜索）大大缩小查询范围；索引针对的是单个字段或者某些字段，本身的数据量比一条记录中的数据量要少得多，所以即使是通过扫描查询索引也比扫描数据库表本身要快得多；知识扩展树结构最大的优点就是查询性能高，所以凡是需要提高查询性能的都可以考虑树。现实中确实有这样的例子，比如：当HashMap中的数据发生冲突时，将链表转为红黑树；数据库索引中使用的B+树；搜索引擎倒排索引中使用的字典树；以上只是浅尝辄止，至此描述了数据库为什么使用B+树索引来提高查询性能以及简单的过程。并没有深究各种数据结构，也没有提及其他索引类型和索引的具体存储格式。目的只是让大家对指数有一个感性的认识。原文链接：https://mp.weixin.qq.com/s/KxSlNnXQSaMemYdqyRCMOg
