Swift 的快速排序集合
使用内存 B 树

• 概述
• 参考文档
• 优化集合：书籍
• 什么是 B 树？
• 为什么使用内存 B 树？
• 标准集合类型的问题清单
• B 树来拯救！
• 实现说明
• 关于导入泛型性能的说明

这个项目提供了一个纯 Swift 中高效的内存 B 树实现，以及几个使用 B 树作为其底层存储的实用排序集合类型。

• Map<Key, Value> 实现从唯一的可比较键到任意值的排序映射。它类似于标准库中的 Dictionary，但它不要求键是可哈希的，它对最坏情况下的性能有强大的保证，并且它以明确的顺序维护其元素。

• List<Element> 实现了任意元素的随机访问集合。它类似于标准库中的 Array，但在任何索引处查找、插入和删除元素都具有对数复杂度。（Array 具有 O(1) 查找，但在任意索引处插入和删除的成本为 O(n)。）连接任何大小的两个列表、将一个列表插入到另一个列表中的任何位置、删除元素的任何子范围或提取任意子列表也是具有 O(log(n)) 复杂度的操作。

• SortedSet<Element> 实现了唯一的可比较元素的排序集合。它类似于标准库中的 Set，但查找、插入和删除任何元素都具有对数复杂度。 SortedSet 中的元素按升序排序。如果源集合中的元素没有交错，则对整个集合进行操作（例如取并集、交集或差集）可能只需要 O(log(n)) 时间。

• SortedBag<Element> 实现了具有可比较元素的排序多重集。这是集合的推广，允许同一值的多个实例。（标准库不包含这样的集合，尽管您可以使用字典通过将键的重数存储为值来模拟一个。）此包中提供的实现分别存储每个重复元素，如果您的元素是具有标识的引用类型，或者您有其他方法来区分相等的元素，这可能会很有用。 SortedBag 操作具有与 SortedSet 中等效操作相同的时间复杂度。

• BTree<Key, Value> 是底层原始集合，它充当上述所有集合的基本存储。它是一个通用的排序键值存储，完全支持具有重复键的元素；它提供了由上述更高级别抽象单独提供的所有操作的总和（以及更多！）。

  BTree 类型是公开的；如果您需要默认未提供的集合风格（例如多重映射），或者如果您需要使用包装器未公开的操作，您可能需要使用它。

所有这些集合都是结构体，它们实现与标准 Swift 集合类型（如 Array 和 Dictionary）相同的写时复制值语义。（事实上，写时复制对这些集合的效果甚至比标准集合更好；继续阅读以了解原因！）

最新版本的 BTree 需要 Swift 4。（支持 Swift 3 的最后一个版本是 4.0.2。）

该项目包括 从其源代码中嵌入的文档注释生成的格式良好的参考文档。

如果您想了解有关此软件包如何工作的更多信息，这本书 优化集合 包含了对该软件包实现的许多算法和优化技巧的详细解释 —— 以及更多更多。它由同一作者撰写，并由 objc.io 的优秀人士出版。购买本书不仅是支持此项目的好方法，还可以让您阅读一些非常有趣的内容。双赢！

B 树 是搜索树，它提供具有出色性能特征的排序键值存储。本质上，每个节点都维护一个自己的元素排序数组，以及另一个子节点数组。该树通过三个约束保持平衡

1. 只有根节点允许小于半满。
2. 没有节点可以大于最大大小。
3. 叶节点都在同一级别。

与其他流行的搜索树（例如 红黑树 或 AVL 树）相比，B 树具有巨大的节点：节点通常包含数百个（甚至数千个）键值对和子节点。

此模块实现了一个“vanilla” B 树，其中每个节点都包含完整的键值对。（另一种流行的类型是 B+ 树，其中只有叶节点包含值；内部节点仅包含键的副本。这在具有固定块大小的外部存储设备上通常更有意义，但对于内存中的实现似乎不太有用。）

树中的每个节点还维护其下所有元素的计数。这使得该树成为一个 顺序统计树，其中可以进行有效的定位查找。

Swift 标准库提供了经过大量优化的数组和哈希表，但省略了链表和基于树的数据结构。这是 Swift 工程团队将资源（精力、代码大小）花费在提供最大性价比的抽象上的结果。

实际上，该库甚至缺少一个基本的 双端队列 构造 —— 尽管 Cocoa 的 Foundation 框架确实在 NSArray 中包含了一个。

但是，某些问题需要更广泛的数据结构。

过去，经常使用链表和低阶搜索树（例如红黑树）；但是，这些构造在现代硬件上的性能受到其大量使用指针的严重限制。

B 树 最初是在 1970 年代发明的，作为慢速外部存储设备的数据结构。因此，它们经过强烈优化，以实现引用局部性：它们更喜欢将数据保存在长连续缓冲区中，并且它们将指针解引用保持在最低限度。（在 B 树中取消引用指针通常意味着从旋转硬盘驱动器读取另一个数据块，与主内存相比，这是一种非常慢的设备。）

今天的计算机具有多层内存架构；它们依靠缓存来保持系统性能。这意味着引用局部性也已成为内存数据结构的一个非常重要的属性。

数组是引用局部性的缩影，因此 Swift stdlib 如此强调 Array 作为通用集合类型是合理的。

例如，使用单个数组来保存排序的项目列表，当有很多元素时，具有相当可怕的（二次）渐近复杂度。但是，在达到某个最大大小之前，简单数组实际上是表示排序列表的最有效方法。

上面的基准很好地证明了这一点：当有很多项目时，将 *n* 个元素插入排序数组的成本为 O(n^2)，但对于许多合理大小的数据集，它仍然比创建具有其花哨的 O(n * log(n)) 复杂度的红黑树快得多。

在曲线的开始附近，最多约 *18,000 个项目*，从外部模块导入的排序数组实现始终比红黑树快约 6-7 倍，其斜率与 O(n * log(n)) 无法区分。

即使在达到二次复杂度之后，在此特定基准中，排序数组也需要大约 *10 万个项目* 才能变得比红黑树慢！

确切的截止点取决于您使用的元素的类型/大小以及编译器的功能。该基准测试使用了微小的 8 字节整数元素，因此数量很大。

该基准测试基于 我自己的红黑树实现，该实现使用单个平面数组来存储节点数据。 更典型的实现 会将每个节点存储在单独分配的对象中，因此它可能会更慢。

上面的图表是一个 双对数图，可以很容易地一目了然地比较竞争算法的复杂度曲线的多项式指数。双对数图上二次算法（例如插入排序数组---绿色曲线）的斜率是线性算法（例如将 *n* 个项目附加到未排序的数组---浅蓝色曲线）或准线性算法（例如插入红黑树，红色曲线）的两倍。

请注意，从 stdlib 导入的集合与从外部模块导入的集合之间的巨大差距是由当前 Swift 编译器/ABI 中的 限制 引起的：当此限制解除后，差距将大大缩小，这将减少您可以获得较低渐近复杂性好处的元素数量。

（这种效果已经在“内联”排序数组（浅绿色）的基准测试中可见（尽管是相反的），这基本上与常规数组（深绿色）的代码相同，只是它在与基准测试循环相同的模块中实现，因此编译器有更多选项来优化掉见证表和其他抽象级别。该行开始上升的时间要早得多，大约有 2000 个项目 —— 想象一下有一个同样快的 B 树实现！或者更好的是，亲自尝试并报告您的结果。生成这样的基准测试需要大量时间和精力。）:-)

这个显着的结果很大程度上归功于操作红黑树需要的大量（对于 CPU 来说，看起来是随机的）内存引用。它们的 复杂的树旋转芭蕾 对我们这些凡人来说看起来非常令人印象深刻，但对于你可怜的 CPU 的精细缓存来说，它更像是喝醉的大象 在鞭打金属音乐会上进行冲撞。

同时，不起眼的 Array 只做它知道的事情：滑动长而连续的内存区域。它一遍又一遍地做这件事，直到让人厌倦。它看起来并不令人印象深刻，但（在一定程度上）它与计算机的工作方式很契合。

因此，小型的 Array 非常适合维护排序列表。但是如果列表变得太长怎么办？B 树的答案很简单，就是将数组一分为二，并在顶部创建一个新的索引树节点，以便它可以快速地在此更复杂的列表结构中找到方向。这些内部索引节点也可以由元素数组和节点引用组成，从而创建一个漂亮的递归数据结构。

由于它们的扇出数非常高，因此 B 树非常浅：对于阶数为 100 的 B 树（实际上相当低），您可以将 10 亿个项目放入不超过五层的树中。

一旦你接受了小数组速度很快，就很容易理解为什么 B 树工作得如此出色：除非它包含的元素超过其阶数，否则 B 树实际上就是一个 Array。因此，对于少量元素，它具有与 Array 相同的性能表现，并且当它变得更大时，它通过从不允许其数组变得太大来防止二次方增长。上面基准测试中的黄色曲线很好地展示了这种行为。

请考虑，典型的 B 树中的每个节点可以容纳大约十个完整的红黑树级别（或 AVL 树或任何你喜欢的二叉树）。在 B 树节点中查找项目仍然需要对节点数组进行二分查找，但此搜索在连续的内存区域上进行，而传统的搜索树则在摆弄加载指针值和解引用它们。

因此，将 B 树用作内存中的数据结构是完全有意义的。

但请考虑一下：在典型的应用程序中，你需要处理十万个已排序项目多少次？甚至两万个？或者甚至只有两千个？ B 树最有趣的优点通常发生在元素数量远远超过十万时。但是，对于低元素计数，B 树并不比数组慢多少（记住，在这种情况下它们就是数组），因此即使有很小的机会计数会变得很大，使用它们也是有意义的。

Array、Dictionary 和 Set 实现的数据结构非常通用：通过这些抽象的简单组合，可以轻松有效地解决大量问题。但是，它们并非没有缺点：您可能遇到过标准集合表现出次优行为的情况

1. 当有很多项目时，在 Array 中间插入和删除可能会很慢。（请记住上一节。）

2. Array、Dictionary 和 Set 的全有或全无的 写时复制行为可能会导致难以检测和修复的性能问题。如果底层存储缓冲区由多个集合实例共享，则修改任何实例中的单个元素都需要创建每个元素的完整副本。

   从代码中完全看不出何时会发生这种情况，甚至更难可靠地检查。您无法（轻松地）编写单元测试来检查是否意外复制了具有值语义的项目！

3. 使用标准集合类型，您通常需要考虑内存管理。

   数组和字典永远不会释放内存，直到它们完全被释放；一个长期存在的集合可能会因为早期元素数量的临时峰值而占用大量内存。这是一种微妙的资源泄漏，很难检测。在内存受限的系统中，浪费太多空间可能会导致进程突然终止。

   将新元素附加到数组，或将新元素插入到字典或集合中，通常是恒定时间的操作，但当集合耗尽其分配的容量时，有时需要 O(n) 时间。执行时间的这些峰值通常是不希望的，但防止它们需要仔细的尺寸分析。
   如果你保留的空间太少，你仍然会遇到峰值；如果你保留的太多，你就在浪费内存。

4. Dictionary 或 Set 中元素的顺序是未定义的，甚至不稳定：在看似简单的更改之后可能会发生变化。具有完全相同元素集的两个集合可能会以截然不同的顺序存储它们。

5. 哈希集合要求它们的键是 Hashable。如果你想使用你自己的类型作为键，你需要自己编写一个哈希函数。编写一个好的哈希函数非常困难，并且更难测试它是否不会为你代码通常使用的值集产生太多的冲突。

6. 哈希冲突的可能性使得 Dictionary 和 Set 不适合需要保证最坏情况性能的任务。（例如，服务器代码可能会因人为的哈希冲突而面临低带宽拒绝服务攻击。）

7. 数组连接需要 O(n) 时间，因为它需要将两个数组中的每个元素的副本放入一个新的连续缓冲区中。

8. 合并字典或取两个集合的并集/交集等都是代价高昂的 O(n) 操作，即使元素根本没有交错。

9. 创建一个可独立编辑的子字典或子集需要对整个集合或整个潜在目标项目集进行逐个元素的迭代。这通常是不切实际的，尤其是在集合很大但稀疏时。

   从数组中获取一个可独立编辑的子数组需要的时间与结果的大小呈线性关系。（ArraySlice 通常很有用，但它作为临时局部变量中的短寿命只读视图最有效。）

这些问题并不总是重要的。事实上，许多有趣的问题可以在不遇到其中任何一个问题的情况下解决。当它们确实发生时，它们造成的问题往往是微不足道的。即使它们造成重大问题，通常也可以通过选择略有不同的算法来轻松解决它们。

但有时你会遇到标准集合类型太慢，并且难以解决的情况。

B 树解决了以上所有问题。（当然，它们也带来了一系列不同的问题。生活很艰难。）

让我们列举一下

1. 无论如何，基于 B 树的数据结构中任何位置的插入或删除都需要 O(log(n)) 时间。

2. 与标准集合类型一样，B 树实现了完整的写时复制值语义。将 B 树复制到另一个变量需要 O(1) 时间；副本的修改不会影响原始实例。

   但是，B 树实现了写时复制的一个大大改进的版本，它不是全有或全无的：树中的每个节点都可以与其他树独立共享。

   如果你需要插入/删除/更新单个元素，即使该树在修改之前完全共享，B 树最多会复制 O(log(n)) 个元素来满足值语义。

3. B 树中的存储管理是细粒度的；你不需要提前为 B 树保留空间，并且它永远不会分配比存储实际元素数量所需更多的内存。

   随着树的增长和缩小，存储会以小增量逐渐分配和释放。仅当修改共享元素时才会复制存储，即使那样也是小批量完成的。

   B 树的性能非常稳定，没有任何不规则的峰值。

   （请注意，在分配中存在一些余地，以便于平衡树。在最坏的情况下，B 树可能仅填充其分配空间的 50%。但是，该比率通常远高于此。）

4. B 树始终按升序键顺序对项目进行排序，并提供高效的位置查找。你可以在 O(log(n)) 时间内获取树中第 i 个最小/最大的项目。

5. B 树的键需要是 Comparable，而不是 Hashable。编写比较运算符通常比哈希函数容易得多；验证实现是否正确工作也容易得多。有缺陷的 < 运算符通常会导致相对容易捕获的明显问题；一个严重冲突的哈希可能会多年未被发现。

6. 对手（或盲目的机会）永远不会产生一组 B 树表现特别糟糕的元素。B 树的性能仅取决于树的大小，而不取决于其内容。（前提是键比较也表现一致。如果你允许使用兆字节的字符串作为键，你将会遇到麻烦。）

7. 任何两个 B 树的连接都需要 O(log(n)) 时间。对于非平凡大小的树，结果将与其输入树共享一些节点，从而推迟了大部分复制，直到需要修改树时。 （这可能永远不会发生。）写时复制在 B 树中真正闪耀！

8. 将两棵 B 树的内容合并到一棵树中，在最坏的情况下需要 O(n) 时间，但如果元素没有太糟糕地交错，它通常可以通过一次将整个子树链接到结果中来在 O(log(n)) 时间内完成。

   在 B 树的键上进行集合运算（例如计算交集、减法集、对称差等）也利用相同的技巧来获得巨大的性能提升。如果输入树是同一原始树的修改版本，则这些操作还可以跳过对输入之间共享的整个子树的逐个元素处理。

9. B 树的 SubSequence（子序列）也是一棵 B 树。你可以随意地分割 B 树：获取任何前缀、后缀或子范围的完全独立的副本只需 O(log(n)) 的时间复杂度。然后，你可以将提取的子树插入到另一棵树中；无论你想要将其放置在树中的哪个位置，这同样需要 O(log(n)) 的时间复杂度。（但是，你需要保持键的顺序正确。）

• BTree 是一个具有写时复制值语义的泛型结构体。在内部，它将其数据存储在具有固定最大尺寸的节点中，这些节点排列成树状结构。BTree 类型提供了一整套经过精心调整的高级操作，用于处理 B 树的元素。

  节点由引用类型的实例表示，该类型不会作为公共 API 导出。（对单个树节点的底层访问很难做到正确，并且会阻止未来的优化，例如将节点计数移动到父节点。）

• 默认情况下，树的阶数（也称为扇出或最大子节点数）设置使得每个节点存储大约 16KiB 的数据。较大的节点大小会加快查找速度，而插入/删除速度会变慢 - 16KiB 是大多数现代系统上最佳节点大小的良好近似值。（但是，如果你更了解，也可以设置自定义节点大小。请注意，你不能混用不同阶数的树。）因此，在 64 位系统上，保存 Int 元素的 B 树每个节点将存储大约 2047 个元素。哇！

• 单个 B 树节点可以在多个 B 树之间独立共享。当修改（部分或完全）共享的树时，写时复制仅限于克隆受修改实际影响的子树的节点。 这有以下后果：

  • 节点不能包含对其父节点的引用，因为它不一定是唯一的。

  • 共享树的修改通常比一次复制整个集合便宜得多，这是标准集合类型所做的事情。

  • 根节点永远不会在不相等的树之间共享。

• BTree 允许将具有重复键的元素存储在树中。（事实上，List 通过对所有元素使用相同的（空）键来工作。）

  所有采用键来查找元素的方法允许你（可选地）指定 是否要使用第一个或最后一个匹配元素，或者如果你对任何匹配项感到满意。 后一个选项有时更快，因为它通常允许搜索在最顶层的匹配元素处停止。 还有一个选择器查找指定键 *之后* 的元素 —— 这对于确定匹配项范围的结尾位置非常有用。

• 每个节点都会跟踪其整个子树中的项目数量，因此高效的位置查找是可能的。 对于任何 _i_，你可以在 log(n) 时间内获取、设置、删除或插入树中的第 _i_ 个项目。

• 有一个BTreeIterator 和一个 BTreeIndex，它们提供通常的生成器/索引语义。 虽然单个元素查找通常需要 O(log(n)) 次操作，但通过这些接口迭代所有元素需要线性时间。 使用生成器比索引更快，因此应尽可能首选使用生成器。 有一些方法可以从树的中间开始迭代器：从任何偏移量、任何索引或任何键。

• 请注意，forEach 有一个专门的递归实现，这使其成为迭代 B 树的最快方法。 甚至有一个变体允许你在看到足够的项目并想离开循环时停止迭代。

• BTreeCursor 是一种易于使用、通用的批量编辑工具，允许你方便且高效地操作 B 树的元素。 你可以使用游标遍历树的内容，根据需要修改/插入/删除元素，而无需按元素 log(n) 查找开销。 如果你需要插入或删除一堆或连续的元素，最好使用提供的批量删除/插入方法，而不是单独处理它们（范围操作具有 O(log(n)) 的复杂度，而逐个元素处理则需要 O(k * log(n))）。

• 在内部，B 树中的导航基于抽象原语，这些原语维护到树中特定位置的路径，如 BTreePath 协议所述。 此协议直接提供的方法对于方便使用来说太底层了，但该协议具有构建在这些方法之上的扩展方法，这些方法支持熟悉的概念，例如逐步来回移动、跳转到树中的特定偏移量或查找特定键。

  索引、生成器和游标使用它们特定的 BTreePath 实现来表示它们自己的路径风格。 它们都维护从树的根到特定节点的特定槽的节点路径，但细节非常不同

  • BTreeIndex 可能不会对其树持有强引用，因为当你想在某个索引处修改树时，这会干扰写时复制。 因此，索引是 BTreeWeakPath 周围的包装器，它使用弱引用，并且需要非常小心地检测其引用之一何时过时。

  • 同时，BTreeIterator 应该支持对树的内容进行独立迭代，因此它必须包含强引用。 它使用 BTreeStrongPath 来表示其下一个元素的路径。 虽然迭代器只需要能够向前移动一步，但 BTreeStrongPath 支持完整的树导航 API，这使得它在代码库中其他任何我们需要树的只读游标的情况下都非常有用。 例如，树合并算法使用强路径来表示其在输入树中的当前位置。

  • 最后，BTreeCursor 需要维护一个路径，其中每个节点都由游标唯一持有，准备好进行修改。 （游标拥有其自己的树副本，并且在完成之前不会与外界共享它。） 此特殊路径风格由 BTreeCursorPath 实现。 为了加快速度，此结构有意破坏了其当前路径上的节点计数，以实现超快速的逐个元素的插入和删除。 每当路径离开树中某个节点的分支时，都会仔细地重新计算计数。

• 单独创建显式路径来查找或修改树中的单个元素将是过度的，因此 BTree 还提供了一组递归方法，用于实现相同类型的查找和简单修改。 当你需要检索单个项目时，它们的速度更快，但重复调用时效率不高。

• BTree 包含一个批量加载算法，可以从任何排序序列有效地初始化完全加载的树。 如果你希望稍后将数据插入树的中间，你还可以指定小于 100% 的填充因子； 留出一些可用空间可以减少保持树平衡的工作量。 批量加载器可以选择为你过滤掉重复的键。 它会验证元素是否按正确的顺序排列，如果不是，则会陷入困境。

  批量加载器基于一个通用的 BTreeBuilder 结构，该结构专门用于将元素附加到新创建的树。 除了单个元素之外，它还支持有效地附加整个 B 树。 这在优化的树合并算法中非常有用。

• 从元素的未排序序列构造 B 树 会将元素逐个插入树中； 不会分配缓冲区来在将元素加载到树中之前对其进行排序。 这比一次一个地调用 插入方法 更有效，但可能仍然比快速排序慢。（因此，如果你能节省额外的内存，请自行排序元素。）

• 该软件包包含 O(log(n)) 方法来 将一系列元素提取为新的 B 树 以及 将 B 树插入到另一棵 B 树中。 （但是，键需要保持正确排序。）

• 合并操作（例如 BTree.union 和 BTree.symmetricDifference）经过高度调整，可以检测到何时可以跳过其输入上的整个子树，根据需要将它们链接到结果中或跳过其内容。 对于包含长串不同元素的输入树，这些操作可以在短至 O(log(n)) 时间内完成。 这些算法在称为 BTreeMerger 的通用树合并构造之上表达。

当前版本的 Swift 编译器无法特化从标准库以外的外部模块导入的泛型类型。（事实上，将标准库视为每次都作为每个 Swift 模块的一部分重新编译，而不是作为不透明的外部二进制文件链接进来，这种说法并没有完全错误。）

这种限制极大地限制了从外部模块导入的集合类型所能实现的原始性能，尤其是当它们使用简单的、极易优化的值类型（如 Int 甚至 String）进行参数化时。依赖于 import 将导致集合保存这些最基本的值类型时出现10-200 倍的减速。（对于引用类型，这种影响会大大降低。）

在无法访问集合的完整源代码的情况下，编译器无法优化掉诸如虚函数分发表、函数调用以及我们在模块内部已经学会忽略的各种冗余抽象。在跨模块泛型中，即使检索单个 Int 也必须至少经过一次虚表的查找。这是因为实现未特化泛型的代码也会对包含引用类型的类型参数执行，而这些引用类型的引用计数需要维护。

如果原始性能至关重要，那么目前摆脱这种困境的唯一方法是将集合的代码放在你的模块内部。（当然，除了修改标准库以包含这些额外的类型之外——但由于无数显而易见的原因，这是一个坏主意。）然而，让每个模块维护自己的一组集合会非常糟糕，并且会使跨模块边界传输集合实例变得困难或不可能。此外，如果这种策略被多个模块使用，将会导致 C++ 模板风格（或更糟糕）的代码爆炸。一个更好（但仍然不太令人满意）的变通方法是使用从特化中获益最多的单个模块编译集合代码。其余模块仍然可以访问它，只是速度会慢得多。

Swift 编译器团队计划在未来的编译器版本中解决此问题，例如，允许库作者手动为预定义的类型参数集特化泛型。