B 树和 B+ 树有什么区别？( 二 ) _B

所以按照这个思路，我们需要做的是将数据按照订单 ID 排好序，查询的时候就可以应用二分查找了。而且按照二分查找的思路，也可以进行范围查找。比如要查找 [a,b] 之间的数据，可以先通过二分查找找到 a 的序号，再二分找到 b 的序号，两个序号之间的数据就是目标结果。
但是直接在原始数据上排序，我们可能会把数据弄乱，常规做法是设计冗余数据描述这种排序关系——这就是索引。下面我通过一个简单的例子告诉你为什么不能在原始数据上直接排序。
假设我们有一个订单表，里面有订单 ID 和金额。使用列存储做演示如下：
订单 ID 列：
10005 10001 ……
订单金额列：
99.00 100.00 ……
可以看到，订单（10001）是第 2 个订单。但是进行排序后，订单（10001）会到第 1 个位置。这样会弄乱订单 ID（10001）和金额（100.00）对应的关系。
因此我们必须用空间换时间，额外将订单列拷贝一份排序：
10001，2，10005，1
以上这种专门用来进行数据查询的额外数据，就是索引。索引中的一个数据，也称作索引条目。上面的索引条目一个接着一个，每个索引条目是 <订单 ID, 序号> 的二元组。
如果你考虑是行存储（比如 MySQL），那么依然可以生成上面的索引，订单 ID 和序号（行号）关联。如果有多个索引，就需要创造多个上面的数据结构。如果有复合索引，比如 <订单状态、日期、序号> 作为一个索引条目，其实就是先按照订单状态，再按照日期排序的索引。
所以复合索引，无非就是多消耗一些空间，排序维度多一些。而且你可以看出复合索引和单列索引完全是独立关系，所以我们可以认为每创造一组索引，就创造了一份冗余的数据。也创造了一种特别的查询方式。
接下来，请分析一个非常核心的问题：上面的索引是一个连续的、从小到大的索引，那么应不应该使用这种从小到大排序的索引呢？例如，我们需要查询订单，就事先创建另一个根据订单 ID 从小到大排序的索引，当用户查找某个订单的时候，无论是行存储、还是列存储，我们就用二分查找查询对应的索引条目。这种方式，我们姑且称为线性排序索引——看似很不错的一个方式，但是并不是非常好的一种做法。
二叉搜索树
线性排序的数据虽然好用，但是插入新元素的时候性能太低。如果是内存操作，插入一个元素，需要将这个元素之后的所有元素后移一位。但如果这个操作发生在磁盘中呢？这必然是灾难性的。因为磁盘的速度比内存慢至少 10-1000 倍，如果是机械硬盘可能慢几十万到百万倍。
所以我们不能用一种线性结构将磁盘排序。那么树呢？比如二叉搜索树（Binary Serach Tree）行不行呢？利用磁盘的空间形成一个二叉搜索树，例如将订单 ID 作为二叉搜索树的 Key 。
如下图所示，二叉搜索树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点。而且，因为索引条目较少，确实可以考虑在查询的时候，先将足够大的树导入内存，然后再进行搜索。搜索的算法是递归的，与二分查找非常类似，每次计算可以将问题规模减半。当然，具体有多少数据可以导入内存，受实际可以使用的内存数量的限制。

文章插图

在上面的二叉搜索树中，每个节点的数据分成 Key 和 Value 。Key 就是索引值，比如订单 ID 创建索引，那么 Key 就是订单 ID 。值中至少需要序号（对行存储也就是行号）。这样，如果们想找 18 对应的行，就可以先通过二叉搜索树找到对应的行号，然后再去对应的行读取数据。

文章插图

二叉搜索树是一个天生的二分查找结构，每次查找都可以减少一半的问题规模。而且二叉搜索树解决了插入新节点的问题，因为二叉搜索树是一个跳跃结构，不必在内存中连续排列。这样在插入的时候，新节点可以放在任何位置，不会像线性结构那样插入一个元素，所有元素都需要向后排列。
那么回到本质问题，在使用磁盘的时候，二叉搜索树是不是一种合理的查询结构？