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

• 概览
• 参考文档
• 优化集合：一本书
• 什么是B树？
• 为什么使用内存中B树？
• 标准集合类型的常见问题列表
• B树拯救！
• 实现注释
• 关于导入泛型性能的备注

概览

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

• Map 实现了一个从独特的可比较键到任意值的排序映射。它类似于标准库中的 Dictionary，但不需要键是可哈希的，它在最坏情况性能上有强保证，并且保持其元素在定义良好的顺序中。

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

• SortedSet 实现了一个唯一可比较元素的排序集合。它类似于标准库中的 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-树是什么？

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

1. 只有根节点允许不足一半满的状态。
2. 没有节点可以超过最大容量大小。
3. 所有叶子节点都在同一级别上。

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

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

树中的每个节点也会维护其下所有元素的计数。这使得树成为一个有序统计树，可以实现高效的定位查找。

为什么需要内存中的B树？

Swift标准库提供了高度优化的数组和哈希表，但省略了链表和基于树的数据库结构。这是Swift工程团队在提供最大效益的抽象上投入资源（努力、代码大小）的结果。

确实，库中甚至缺少一个基本的双向队列结构—尽管Cocoa的Foundation框架在NSArray中包含了这样一个结构。

然而，一些问题需要更多种类的数据结构。

过去，经常使用链表和像红黑树这样的低阶搜索树；然而，这些结构在现代硬件上的性能受其指针使用过度而大大受限。

B树最初在20世纪70年代发明，作为慢速外部存储设备的数据结构。因此，它们在引用的局部性方面得到了强烈的优化：它们更倾向于在长连续缓冲区中保持数据，并尽量减少指针解引用。（在B树中解引用一个指针通常意味着从旋转的硬盘驱动器中读取另一个数据块，而与主内存相比，它是一个极其慢的设备。）

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

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

例如，使用单个数组来存储有序列表的项目时，如果有许多元素，其渐近复杂度（二次方）是相当糟糕的。但是，在某个最大尺寸以内，简单的数组实际上是有序列表表示的最高效方法。

上面的基准测试很好地说明了这一点：当有很多项目时，将n个元素插入有序数组的花费为O(n^2)，但对于许多合理尺寸的数据集，它仍然比创建一个复杂的红黑树要快得多，红黑树的复杂度为O(n * log(n))。

在曲线的近端，到大约一万八千项，从外部模块导入的有序数组实现的速度始终比红黑树快6-7倍，其斜率与O(n * log(n))无法区分。

即使它达到了二次方复杂度，在这个特定的基准测试中，当项目达到大约一百万时，有序数组才变得比红黑树慢！

确切的分界点取决于你处理的元素类型/大小以及编译器的功能。这个基准测试使用了微小的8字节整数元素，因此这个数字非常大。

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

上面的图表是一个对数对数图，它使人们可以一目了然地比较竞争算法的复杂度曲线的多项式指数。在对数对数图上二次算法的斜率（如插入有序数组——绿色曲线）是线性算法（如将n个项目追加到未排序数组——浅蓝色曲线）或准线性算法（如插入到红黑树，红色曲线）斜率的两倍。

请注意，从stdlib导入和从外部模块导入的集合之间存在很大的差距，这是由当前Swift编译器/ABI的一个限制造成的（请参阅性能限制）：当这个限制放开时，差距将显著缩小，这将减少您能够从更低的渐进复杂性中获益的元素计数。

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

这一显著结果在很大程度上归因于操作红黑树所需的庞大数量的（对CPU来说看似随机的）内存引用。他们复杂的树旋转芭蕾舞对我们这些凡人来说看起来非常令人印象深刻，但对你那脆弱的CPU缓存来说，它看起来更像是醉酒的大象在重金属音乐会上狂欢。

与此同时，谦逊的Array只做它知道的事情：滑动围绕长连续内存区域。它一遍又一遍地这样做，直到反胃。它看起来不令人印象深刻，但（在一定范围内）它与计算机的工作方式很好地匹配。

所以，一个小Array非常适合维护有序列表。但如果列表太长怎么办？B-树的回答是简单地将与一半的数组，并创建一个新的索引树节点在顶上，以便它可以快速找到在更复杂的列表结构的方法。这些内部索引节点也可以由元素数组和节点引用数组组成，创建一个很棒递归数据结构。

因为它们的一致性数量很高，B-树非常浅：对于一个顺序为100的B-树（这实际上相当低），你可以在不超过五个级别的树中放入十亿个项目。

一旦你接受小数组很快，你很容易看出为什么B-树工作得很好：除非它的元素数量超过其顺序，否则B树实际上就是Array。所以对于少量元素，它具有与Array相同的性能行为，当它变大时，它通过永远不让它的数组变得太大来防止二次上升。上面基准测试中的黄色曲线很好地展示了这种行为。

考虑到一个典型的B-树节点可以存放大约十个全层的红黑树（或AVL树或你喜欢的任何二叉树）。在一个B-树节点中查找项仍然需要在节点数组中进行二分搜索，但这个搜索是在连续内存区域上进行的，而传统的搜索树则是在加载指针值并解引用它们。

因此，将B-树用作内存数据结构是perfect sense。

虽然如此，想想看：在典型应用程序中，你需要多少次处理十万有序项目？或者甚至两万？或者甚至只是两千？B-树最有趣的利益通常在元素计数远远超过十万的情况下出现。然而，B-树对于低元素计数并没有慢多少（记住，在这种情况下，它们确实是数组），所以，只要有点可能计数会变得很大，使用它们就很有意义。

标准集合类型问题清单

Array、Dictionary 和 Set 实现的数据结构非常灵活：大量问题可以通过这些抽象的简单组合轻松有效地解决。然而，它们并非没有缺点：你可能遇到过标准集合在行为上不够理想的例子。

1. 当数组中有大量元素时，插入或删除中间的元素可能会很慢。（不过，请记住前一个部分。）

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

   这种情况在代码中并不明显，而且可靠地检查它更困难。您（不容易）编写单元测试来检查值语义项的意外复制！

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

   数组和字典决不释放内存，直到它们完全解除分配；由于元素数量的早期、暂时的增加，长期存在的集合可能由于内存泄漏而占用大量内存。这是一种难以发现的微妙资源泄漏形式。在内存受限的系统中，浪费太多空间可能会导致进程突然终止。

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

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

5. 哈希集合需要它们的键是 Hashable。如果您想使用自己的类型作为键，您需要自己编写哈希函数。编写好的哈希函数很困难，测试它是否会产生太多碰撞也很困难，特别是对于代码将通常使用的值集。

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

7. 数组连接需要 O(n) 时间，因为它需要将两个数组的所有元素复制到一个新的连续缓冲区中。

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

9. 创建可独立编辑的子字典或子集需要遍历整个集合或潜在目标项的整个集合。这在集合大小但稀疏时往往不切实际。

   从数组中获得可独立编辑的子数组所需的时间与结果大小成正比。（ArraySlice 有时很有用，但它最有效地作为临时局部变量中的短期只读视图。)

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

但有时你会遇到一个情况，其中标准集合类型速度太慢，围绕它们校正会非常痛苦。

B树救命！

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树的子序列也是一个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实现。为了加速，这个结构故意破坏当前路径上的节点计数，以允许快速的元素级插入和删除。当路径在树中移出节点的分支时，会仔细重新计算这些计数。

• 只为查找或修改树中的单个元素而创建特定的路径会 overwritten，所以 BTree 还提供了一系列递归方法，以实现类似的查找和简单的突变。当需要检索单个项目时，它们速度快，但是当重复调用时，效率不高。

• BTree 包含一个批量加载数据算法，可以高效地从任何排序序列初始化完全加载的树。如果您预计稍后要在树的中间插入数据，也可以指定小于100%的填充因子；留出一些空间可能可以减少保持树平衡的工作。批量加载程序可以选择性地为您过滤掉重复的键。它还验证元素是否正确排序，如果不正确则捕获错误。

  批量加载程序基于一个通用的BTreeBuilder结构体，该结构体专门负责将元素追加到新创建的树中。除了单个元素外，它还支持高效地追加整个B树。这在优化的树合并算法中很有用。

• 从未排序的元素序列构建B树时，会逐个将元素插入树中；在将元素加载到树中之前，不会分配缓冲区来对元素进行排序。这比逐个调用插入方法要高效，但可能仍然比快速排序要慢。（所以如果你可以节省额外的内存，请在自己的领域中对这些元素进行排序。）

• 该包包含O(log(n))方法来从一个新的B树中提取一个范围元素，以及将一个B树插入到另一个B树中。（尽管如此，键仍需正确排序。）

• 合并操作（例如BTree.union和BTree.symmetricDifference）已高度优化，以检测何时可以跳过输入中的整个子树，根据需要将它们链接到结果或跳过它们的声明。对于包含大量不同元素的输入树，这些操作可以以O(log(n))的时间完成。这些算法是基于名为BTreeMerger的通用树合并结构。

关于导入泛型性能的注释

Swift编译程序当前的版本无法对从除了标准库以外的外部模块导入的泛型类型进行特化。（实际上，可以说标准库编译是最新的，因为它每次与Swift模块一起编译，而不是作为一个不透明的外部二进制链接进来。）

这种限制对外部模块导入的集合类型所能实现的原始性能有了相当的限制，特别是如果它们与简单的、极其优化的值类型（如Int或甚至String）参数化时。

由于无法访问整个集合的源代码，编译器无法优化掉类似虚拟调度表、函数调用和模块内部我们大多忽略的其他冗余代码。在跨模块泛型中，即使只检索单个Int，也必然会通过至少一个虚拟表的查找。这是因为实现未特化的泛型的代码也会为包含引用类型的类型参数执行，这些引用计数需要维护。

如果原生性能至关重要，目前唯一摆脱这个困境的方法是将集合的代码放在你的模块中。（当然，除之外，还可以通过黑客stdlib来包含这些额外的类型——但这有千百个明显的坏主意。）但是，让每个模块维护其自身的集合集合会非常糟糕，此外，它还会使得在不同模块边界之间传递集合实例变得困难和不可能。而且，如果这种情况在许多模块中使用，会导致C++模板风格（或更糟）的代码爆炸。一个更好的（但仍相当令人不满意）的折衷方法是将集合代码与受特化利润最大的单个模块一起编译。其他模块仍可以访问它，只是速度会慢很多。

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