索引设计的树结构选择
索引设计是数据库非常精髓的一部分内容，在进入到具体细节之前，就先从索引的数据结构设计上的思路开始吧。
二叉查找树
最近有一部漫改动画特别火——《鬼灭之刃》，属于比较经典传统的热血漫画，一直有关注ACG相关信息的同学肯定也不用我推荐了。不关注ACG的同学，如果对《火影忍者》《海贼王》这种类型的热血动画比较喜欢，鬼灭的动画应该也会喜欢。这部作品主要讲述的是人和鬼之间的战争，然后人类方主要依靠一种叫做"呼吸法"(作者是JOJO粉丝)的技巧战斗，呼吸法有各种各样的属性，比如风之呼吸，雷之呼吸等等，但所有的呼吸都是一种呼吸的变体——日之呼吸。
日之呼吸在所有呼吸法中的地位，就相当于二叉查找树在索引相关的查找树之中的地位，大多数人都不会用，但其思想是贯穿在所有衍生出来的查找树之中的。所以在谈到能在生产环境下具体使用的树结构之前，先从祖先开始认识。
这种数据结构如果常刷Leetcode的肯定不会陌生，二叉查找树简称BST(Binary Search Tree)，树相关的入门题常客，因为其性质确实非常直观，有如下几点：
- 若任意节点的左子树不空，则左子树所有节点都小于根节点的值
- 若任意节点的右子树不空，则右子树所有节点都大于根节点的值
- 任意节点左右子树都是二叉查找树
- 没有键值相等的节点
先来探讨一下为什么数据库的索引实现总是偏向于查找树这样一种数据结构。因为数据库的特点就在于增删改查，如果用链表，增删为O(1)满足要求，查起来速度为O(n)不合格。如果用数组，查为O(1)满足要求，增删又为O(n)不合格了，所以需要一种能够把更新和查询速度折中的方案。回头看二叉查找树，增删改查通常都为O(logN)，就比较符合数据库的要求了。
当然如果BST已经能完全满足数据库要求，那我这篇文章就完结了，收工睡觉可喜可贺。但正因为BST规则约束的简洁，也说明不可避免一些特殊情况下会有局限性。比如当根节点为最值时BST就会退化为线性链表，效率会退化为O(n)。
这肯定是不能接受的。不过BST的思想在大方向上是满足需求的，只需要考虑如何避免这种特殊情况即可，也就有了接下来谈到的各种BST衍生。
平衡树
很自然的想法，有特殊情况解决就可以。平衡树为了解决二叉查找树不平衡的特殊情况，就是在二叉查找树的基础上再附带一条新的特点：
- 所有的叶子节点的深度趋于平衡
至于用什么具体的手段去平衡这棵树就有多种多样的方法了。但需要注意一点，结果越严格平衡，维持平衡的代价也就越高，如何取舍两者间的比例也是需要根据具体场景考虑的。经典的比如AVL树，严格限制任一节点对应的两棵子树的最大高度差为1，按照结果来说是能严格控制效率为O(logN)的，但每次更新时都需要以相当高的代价去维持AVL的规则，所以生产环境下AVL树的应用场景极少，取而代之的是另外一种折中的平衡树方案——红黑树。
红黑树
同样为平衡树，和AVL树类似，在二叉查找树的基础上增加了如下约束：
- 节点是红色或黑色
- 根是黑色
- 每个红色节点必须有两个黑色子节点
- 从任一节点到每个叶子节点的所有简单路径都包含相同的黑色节点
具体实现细节比较复杂，就不在这里分析了，只需要知道一点，这些约束确保了红黑树的一个特性：
- 根到叶子节点的最长路径不多于最短路径的两倍长度
红黑树这种松散的平衡树方案导致维护需要的代价不算高，带来的效率提升也很可观，就非常适合具体场景了。Linux的进程调度以及Java中的TreeMap实现等等都用到了红黑树。所以儒家的"中庸之道"还是有一定道理的，像AVL树这样太严格了不行，像二叉查找树这样太松散了也不行，适中的才是最泛用的。
那么到这里，数据库的索引设计的方案是不是就可以定下来为红黑树了呢？在下定论之前必须理解一点：因为数据库索引外部存储的特性，磁盘I/O才是性能的关键点，而磁盘I/O的代价是远高于内存读取的。因为红黑树是二叉的，存储数据变多时，高度也就是磁盘I/O次数会变得难以控制，所以我们需要一种能够降低高度的查找树方案。
平衡多路查找树
数据量不变的情况下要降低高度，最直观的想法就是让每层的节点变多，实际上也就是这么做的。平衡多路查找树，简称B树，每个节点由2叉变为m叉，这个m就是这颗B树的阶。一颗m阶的B树具有如下特点：
- 根节点至少两个子节点
- 每个中间节点都包含k-1个元素和k个子节点，其中m/2 <= k <=m
- 每个子节点都包含k - 1个元素，其中m/2 <= k <= m
- 所有叶子节点同层
- 每个节点中的元素从小到大按升序排列，节点中的k-1个元素就相当于k个子节点的边界之一，查询时会比较目标值和元素的大小指向对应范围的子节点
以这颗B树为例，看查找一个为9的元素会经历哪些步骤：
- 与根节点比较，9小于17，指向P1对应的子节点磁盘块2
- 在磁盘块2中比较，9在8到12之间，指向P2对应的磁盘块6
- 在磁盘块6中比较，9在9到10之间，找到目标元素
可以看到，比较的次数并不会比在红黑树中少，但因为树的深度低，磁盘I/O次数少，比较都是在内存中进行的，所以效率是比红黑树要高的，也满足实际应用中的需要。
B+树
在B树的基础上，又衍生出了B+树，有如下改动：
- 有k个子节点，就有k个元素，相比于B树会多存储一个来自父节点的元素，这个元素正是该节点的边界之一
- 中间节点的元素不保存数据记录，仅用于指针记录，所有数据记录都放在叶子节点中
- 叶子节点构成一个有序链表，同时叶子节点内部的数据记录也从小到大按升序排列
以这颗B+树为例，看查找一个为16的元素会经历哪些步骤：
- 与根节点计较，16在1和18之间，由指针记录找到磁盘块2
- 在磁盘块2中比较，16在8和14之间，由指针记录找到磁盘块7
- 在磁盘块7中找到数据记录
查询步骤看起来和B树差不多，但有几个关键变动：
- B+树查询效率更稳定，因为每次都需要走到叶子节点，而B树可能在中间节点就找到数据
- B+树查询效率更高，因为中间页不需要保存数据记录，同样大小的磁盘页可以容纳更多节点，阶数更大，深度更低，磁盘I/O更少
- B+树范围查询可以使用有序链表，而B树只能中序遍历
B和B+的取舍
到这里我们似乎已经可以下一个定论了，数据库的索引实现用B+树很合适，实际上MySQL也确实是这么实现的。不过还有一点值得讨论，MongoDB的实现却是用的B树。B+树难道不是B树的完全上位吗？
关键就在MongoDB的数据模型上，因为MongoDB是聚合型的数据库，使用BSON格式保存数据，需要适用于性能要求高的场景。而B树的key和data正好符合聚合模型，同时对稳定性的要求低于效率，所以B树有可能在中间节点就可能返回数据，时间复杂度最好的情况下能达到O(1)，相比于B+树的稳定更适用。
小结
这篇文章分析了查找树在数据库索引设计这样一种具体场景的取舍，并没有深究数据结构的具体实现。算法的实现细节是次要的，关键在于弄懂不同数据结构的优劣以及应用场景，在今后可能遇到的实际问题中选择合适的方案。下一篇文章就要分析在选定数据结构之后，索引的具体实现了。
-- EOF --