我正在阅读数据结构，尤其是不可变的数据结构，例如CouchDB中使用的append-only B+ tree和Clojure中使用的Hash array mapped trie以及其他一些功能编程语言。
在内存中运行良好的数据结构可能无法在磁盘上正常运行的主要原因是，由于碎片（与普通的二叉树一样），导致磁盘寻道上花费的时间。
但是，HAMT也很浅，因此只需要B树即可进行查找。
另一个建议的原因是，从数组映射的树中删除比从B树中删除更为昂贵。这是基于我们正在讨论密集向量的假设，并且在将两者用作哈希映射时均不适用。
而且，似乎B树执行了更多的重新平衡，因此以仅追加的方式使用它会产生更多的垃圾。
那么，为什么CouchDB以及几乎所有其他数据库和文件系统都使用B树？
分形树？日志结构的合并树？头脑=吹
现实生活中的B树使用的度数为数千，而HAMT的度数为32。HAMT的度数为1024是可能的，但是由于popcnt一次处理32或64位，因此速度较慢。
最佳答案
之所以使用B树，是因为它们是一种易于理解的算法，可以实现“理想”的排序读取成本。因为密钥是排序的，所以移动到下一个或上一个密钥非常便宜。
HAMT或其他哈希存储以随机顺序存储密钥。密钥是通过它们的确切值来检索的，没有找到下一个或上一个密钥的有效方法。
关于程度，通常通过选择页面大小间接选择。 HAMT最常用于内存中，其页面大小适合高速缓存行，而btree最常用于辅助存储，其中页面大小与IO和VM参数有关。
日志结构合并（LSM）是排序订单存储的另一种方法，它通过权衡一些读取效率来实现更佳的写入效率。对于读取-修改-写入工作负载而言，达到读取效率的问题可能是一个问题，但是未缓存的读取越少，与btree相比，提供更多的LSM可以提供更好的总体吞吐量-最坏情况下的读取延迟会更高。
LSM还提供了更广泛性能的承诺。将新数据放入适当的位置是“延迟的”，通过控制延迟清除工作与实际工作的比例，可以调整读写效率。从理论上讲，具有零延迟的理想LSM是btree，具有100％延迟的理想LSM是对数。
但是，LSM更像是算法的“家族”，而不是像btree这样的特定算法。它们的使用日益普及，但是由于缺乏实际的最佳LSM设计而受到阻碍。 LevelDB / RocksDB是更实用的LSM实现之一，但远非最佳。
实现写吞吐量效率的另一种方法是通过写延迟对btree进行写优化，同时尝试保持其最佳读吞吐量。
分形树，穿梭树，分层树是这种类型的设计，代表btree和LSM之间的混合灰色区域。它们不是将写操作推迟到脱机进程，而是以固定方式摊销写默认设置。例如，这种设计可能代表固定的60％写延迟分数。这意味着它们无法达到LSM的100％延迟写入性能，但是它们还具有更可预测的读取性能，从而使它们成为btree的更实用的即插即用替代品。 （与商业Tokutek MySQL和MongoDB分形树后端一样）