系统与数据库2017citeseerx.ist.psu.edu
现代 B 树技术（2011）
Modern B-Tree Techniques (2011)
专业 · 约 180 分钟读完前置知识：数据库系统基础、B+树与索引结构、并发控制与日志恢复
导读
这是 Goetz Graefe 于 2011 年发表的关于现代 B 树技术的综述性论文，讨论 B 树在数据库系统中的关键技术，包括多字段索引、并发控制、日志与闩锁等。评论指出作者是 B 树领域的权威人物，并围绕 B 树与哈希索引的优劣、闪存/非易失内存的影响以及综述的时效性展开讨论。
HN 关注点：一方面因为作者 Goetz Graefe 是 B 树领域的代表人物并获 SIGMOD Codd 创新奖，另一方面讨论聚焦于 B 树相对哈希索引的优势是否仍成立，以及这篇 2011 年综述对闪存、日志/锁等技术的描述是否已经过时。
HN 评论精选
这几条评论里：质疑 2 补充 2
补充介绍作者 Goetz Graefe 是 B 树领域的权威，并补充其获奖信息和锁相关论文链接。
可能有人不知道，Goetz Graefe 算是 B 树的守护圣人。他最近因贡献获得了 SIGMOD Codd 创新奖：链接。他还对 B 树中的锁有很多论述：链接。
makmanalp查看英文原文
For those who don't know, Goetz Graefe is sort of the patron saint of btrees. He recently won the Sigmod Codd innovations award for his contributions: https://sigmod.org/sigmod-awards/people/goetz-graefe-2017-sigmod-edgar-f-codd-innovations-award/ He also has a lot to say about locking in B-trees: http://15721.courses.cs.cmu.edu/spring2016/papers/a16-graefe.pdf
补充同意 B 树优于哈希的论据，但指出前缀搜索在低选择性字段上未必有用，并认为快速字节可寻址 NVM 可能改变哈希与 B 树的权衡。
> 支持 B 树而非哈希索引的最有力论据，大概涉及多字段索引和键值非均匀分布。多字段哈希索引要求所有字段的搜索键都存在才能计算哈希值；而 B 树索引可以高效支持索引键前缀的精确匹配查询，即任意数量的前导索引字段。 是的，但如果索引中没有任何一列/字段具有足够的选择性，那么按前缀搜索 B 树可能也帮不上什么忙。不过别误会：我完全同意文中给出的 B 树优于哈希表的理由。虽然最新的存储技术（尤其是非常快的字节可寻址非易失内存）——对本综述来说太新了——很可能会改变局面。当你有快速的字节可寻址存储时，不读取页面会带来收益，在这种情况下哈希表可能比 B 树涉及更少的访问，不过我猜 B 树最终仍会成功适应。
cryptonector查看英文原文
> Probably the strongest arguments for B-trees over hash indexes pertain to multi-field indexes and to nonuniform distributions of key values. A hash index on multiple fields requires search keys for all those fields such that a hash value can be calculated. A B-tree index, on the other hand, can efficiently support exact-match queries for a prefix of the index key, i.e., any number of leading index fields Yes, well, if none of the columns/fields in the index are sufficiently selective, then the ability to search a B-tree by prefix may not do you much good. Don't get me wrong though: I fully agree with all of the given reasons for B-tree superiority to hash tables. Although the newest storage technologies (particularly very fast byte-addressable NVMs) -- too new for TFA -- might well change things. When you have fast byte-addressable storage it will pay to not read pages, and hash tables may yet involve fewer accesses than B-trees in that case, though I suspect B-trees will successfully adapt anyways.
质疑批评综述过多篇幅讲 RDBMS 中的日志/锁/闩锁等已过时内容，且完全未涉及不可变/持久 B 树。
这是一篇有趣的综述。我很惊讶它花了那么多篇幅在关系数据库管理系统的背景下说明 B 树，因为那里很多概念其实与 B 树没有特定联系。它用了大量篇幅讲日志、锁和闩锁。这些在直到过去十年都还在业界大量使用，现在全都过时了。文中一次都没提不可变/持久 B 树。在这篇综述覆盖的时间范围内，真的没有关于该主题的学术论文吗？
hyc_symas查看英文原文
Well, it's an interesting survey. I'm surprised at how much space it devoted to illustrating B-trees in the context of RDBMSs as a lot of the concepts there really had no specific connection to B-trees. So much space devoted to logging, locking and latches. All heavily used in the industry up till the last decade. All obsolete now. Not a single mention of immutable/persistent B-trees. Were there really no academic papers on the topic written in a time covered by this survey?
质疑指出论文发表于 2011 年，其中对闪存即将改变内存层次的预测已经过时，提醒读者注意时效性。
这篇是 2011 年的，以防你错过。我一开始被这样的句子搞糊涂了：“闪存、闪存设备和其他固态存储技术即将改变计算机系统乃至数据管理中的内存层次结构。”直到我抬头看了出版日期。
mistercow查看英文原文
This is from 2011, in case you missed that. I was confused by sentences like: >Flash memory, flash devices, and other solid state storage technology are about to change the memory hierarchy in computer systems in general and in data management in particular. until I looked up at the publication date.
历次讨论
- 2017Hacker News 讨论帖314 分 · 11 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选学习型索引结构之论证
The Case for Learned Index Structures
提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引…
系统与数据库2017 · 398 分 · 66 评 · 引用 25进阶 · 约 60 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选