Pep*_*ijn 6 couchdb b-tree clojure immutability
我正在阅读数据结构,特别是不可变的数据结构,如CouchDB中使用的仅附加B +树和Clojure中使用的Hash数组映射trie以及其他一些函数式编程语言.
在内存中运行良好的数据结构在磁盘上运行良好的主要原因似乎是由于碎片而花费在磁盘搜索上的时间,就像普通的二叉树一样.
然而,HAMT也非常浅,因此不需要比B树更多的搜索.
另一个建议的原因是来自阵列映射的trie的删除比来自B树的更昂贵.这是基于我们正在讨论密集向量的假设,并且在将其用作哈希映射时不适用.
更重要的是,似乎B树进行了更多的重新平衡,因此以仅附加方式使用它会产生更多垃圾.
那么为什么CouchDB和几乎所有其他数据库和文件系统都使用B树？
[编辑]分形树？日志结构合并树？心灵=吹
[编辑]现实生活中的B树使用数千的度数,而HAMT的度数为32.可以使用1024度的HAMT,但由于popcnt一次处理32或64位,因此速度较慢.
使用B树是因为它们是一种易于理解的算法,可实现"理想的"分类顺序读取成本.由于密钥已排序,因此移动到下一个或上一个密钥非常便宜.
HAMT或其他哈希存储,以随机顺序存储密钥.密钥按其确切值检索,并且没有有效的方法来查找下一个或上一个密钥.
关于度,通常通过选择页面大小来间接选择.HAMT最常用于内存中,页面大小适用于缓存行,而btree最常用于辅助存储,其中页面大小与IO和VM参数相关.
Log Structured Merge(LSM)是一种不同的排序顺序存储方法,它通过牺牲一些读取效率来实现更高的写入效率.对于读取 - 修改 - 写入工作负载而言,读取效率的上升可能是一个问题,但是,对于未缓存的读取数量越少,LSM提供的整体吞吐量与btree相比就越大 - 在最坏情况下读取延迟更高.
LSM还提供更广泛性能的承诺.将新数据放入正确的位置是"延迟",通过控制延迟清理工作与实际工作的比例,提供调整读写效率的可能性.理论上,具有零延迟的理想LSM是btree,并且100%-deferral是对数.
然而,LSM更像是算法的"族",而不是像btree这样的特定算法.它们的使用越来越受欢迎,但由于缺乏事实上的最佳LSM设计而受到阻碍.LevelDB/RocksDB是更实用的LSM实现之一,但它远非最佳.
实现写吞吐效率的另一种方法是通过写延迟对写双优执行进行写优化,同时尝试保持其最佳读吞吐量.
分形树,穿梭树,分层树是这种类型的设计,并代表btree和LSM之间的混合灰色区域.他们不是将写入推迟到离线流程,而是以固定的方式对写作失败进行策划.例如,这样的设计可能代表固定的60% - 写入 - 延迟分数.这意味着它们无法实现LSM的100%写入 - 默认性能,但它们也具有更可预测的读取性能,使它们成为更实用的btree替代品.(如商业Tokutek MySQL和MongoDB分形树后端)
小智 3
Btree 按其键排序，而在哈希映射中，相似的键具有非常不同的哈希值，因此彼此存储得较远。现在考虑一个进行范围扫描的查询“给我昨天的销售额”：使用哈希映射，您必须扫描所有映射才能找到它们，使用 sales_dtm 列上的 btree，您会发现它们很好地聚集在一起，并且您确切地知道从哪里开始和停止阅读。