按年被提到
20112011 · 4 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:1103.4282 · cs.DS

Stratified B-trees and versioning dictionaries

分层 B 树与版本化字典
Andy Twigg, Andrew Byde, Grzegorz Milos, Tim Moreton, John Wilkes, Tom Wilkie · 2011

分层 B 树:在空间、查询、更新间取得最优折中的版本化字典

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2011-04-12 · 最近 2018-01-06
6不同的人
3活跃月份
4讨论串
4被引(OpenAlex)

写时复制(CoW)B 树被 WAFL、ZFS、Btrfs 等文件系统和数据库广泛使用,但空间利用率差、更新慢、依赖随机 IO。论文提出 stratified B-tree,优于已知所有半外存版本化 B 树(包括 CoW B 树),是首个在空间、查询和更新性能之间达到最优折中的版本化字典。

HN 为什么提它

HN 上的讨论多围绕发帖时的链接形式,以及有人希望看到它与 LSM 树式的键值存储正面较量。

方法难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1B 树
2写时复制(copy-on-write)
3外存 IO 复杂度模型
4LSM 树

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐jholman · 2011-04

“note that there are actually two papers linked, both interesting.”

提醒链接里其实有两篇论文,都有意思,涉及 SSD 和追加写
Copy-on-write B-tree finally beaten.原评论 ↗
引用wnoise · 2011-04

“I strongly prefer links to the abstract:”

更喜欢链接到摘要页而不是 PDF,针对这篇分层 B 树论文
Copy-on-write B-tree finally beaten.原评论 ↗
引用chalst · 2011-04

“I prefer giving the Arxiv abstract list, which always links to the current version of the PDF.”

更愿意给 arXiv 摘要页,因为它总指向 PDF 的最新版本
Copy-on-write B-tree finally beaten.原评论 ↗
引用eyan · 2016-05

“I'd like to see Stratified B Trees kick LSMs' butts. Or the other way around.”

希望看到 Stratified B-tree 与 LSM 一较高下
An LSM-Tree-based Ultra-Large Key-Value Store for Small Data [pdf]原评论 ↗
被提交为 story · 2 次