算法与计算机科学benjamincongdon.me
B 树：超出我预期的知识量
B-Trees: More Than I Thought I'd Want to Know (2021)
2021 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇博客是作者深入学习 B 树（及 B+ 树）后的总结笔记，介绍了 B 树的结构、变体及其在数据库和文件系统等存储场景中的应用。文章因讲解清晰而广受好评，多次登上 Hacker News 首页。
为什么经久不衰：B 树是数据库和文件系统的基石数据结构，这篇笔记讲解透彻，多年后仍是入门学习的优质参考。
HN 评论精选
从 FAT32 碎片化的亲身经历出发，说明简单文件系统是理解 B 树等高级数据结构价值的最佳入门。
我觉得 DOS 时代的 FAT/FAT32 简单到容易解释，让我们这代程序员在学习技术时有个绝佳的切入点。它不是 B 树、不涉及平衡，就是一个简单的链表，用久了会严重碎片化，需要花一小时“整理磁盘碎片”才能恢复速度。当时我太小不懂原因，但那段经历一直留到大学。大学里我学了 FAT32 的基本原理（虽然过时，但简单到是很好的入门教材），由此明白了为什么我们要转向 B 树这类更高级的数据结构，为什么 B 树更不容易碎片化。我学习过程的重要一环就是当年整理碎片时等待的那几个小时，这些记忆让我深知不用自平衡 B 树存储数据的坏处。也许今天我们没法再让新一代用户在日常中使用 FAT32 这种较差的文件系统了，但至少可以讲讲那些故事，让他们理解为什么现代文件系统数据结构要如此复杂。
dragontamer查看英文原文
I feel like FAT and FAT32 back in the DOS days were so simple and easy to explain, that my generation of programmers have the "sweet point" in terms of learning technology. FAT / FAT32 wasn't about B-trees or balancing or anything. It was a simple linked list, that got severely tangled up during use and required an hour of "defragmenting" to make your hard drive go back at high speed. As a computer user of the time, I was too young / ignorant to know why it happened like that, but that experience stuck with me until college. In college, I learned about how FAT32 filesystem worked fundamentally (though obsolete, its so simple its a great introduction). From there, I learned why we have moved onto more advanced data-structures like B-Trees. Why things like B-trees are less prone to fragmentation. Etc. etc. ---------- A big part of my learning process was the hours of waiting I'd put in to defrag my hard drive back in the day. Those memories stuck with me, I know what the "downsides" are if I don't use a self-balancing B-Tree to store data on a hard drive. Perhaps today, we're no longer at a point where we can just convince legions of new computer-users (or programmers) to use inferior file systems like FAT32 in their daily lives. But we can at least tell stories about those times, so that they can understand why we put so much complexity into our modern filesystem data-structures.
亲手实现 B+ 树极其困难，侧面印证了这一数据结构的复杂性和学习价值。
大学数据库课上我实现过一个简单的 B+ 树（因为数据库常用它）。这是那种很少有人能完整完成的作业，大多数人只完成了不同程度的一部分。我完成了一多半但没能做完。这是一份极其困难的作业，让我印象深刻。它们非常有趣也非常复杂，好文章！
bern4444查看英文原文
I had to implement a simple B+ tree for a databases class in college (since they're often used when implementing databases). It was one of those assignments few people fully completed. Most completed parts of it to varying degrees. I got more than halfway through but wasn't able to complete it. It was an extremely difficult assignment and stands out in my mind. They're very interesting and very complex. Nice article!
推荐 SQLite3 文档中的 B 树磁盘格式说明作为最佳学习资源。
最好的 B 树学习资料是 SQLite3 文档中对它磁盘上 B 树格式的说明。
cryptonector查看英文原文
The best B-tree resource is SQLite3's documentation of its B-tree on-disk format.
自己做玩具数据库时实现 B 树会遇到文中提到的种种问题，推荐这类实践项目。
这真的很棒。我最近尝试构建一个玩具数据库，随后实现了自己的 B 树，结果遇到了文中提到的很多问题。我还写了一篇关于为什么大家都应该做类似项目的文章。
spanspan查看英文原文
This is really cool. I recently attempted to build a toy database, and subsequently implemented my own b-tree ( https://github.com/spandanb/learndb-py). I ended up running into a lot of these issues. I also did a write-up on why everyone should engage in similar projects: https://www.spandanbemby.com/joys-of-database.html
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选