May 2020
Beginner to intermediate
319 pages
7h 3m
Chinese
Content preview from 数据库系统内幕
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
40
｜
第
2
章
或用尽范围谓词为止。
2.3.5
键的数目
纵观文献，你可以找到描述键和子节点偏移量数目的不同方法。[BAYER72] 提到了一个
表示最佳页大小的、依赖于设备的自然数 k。在这种情况下，页可以保存 k 到 2k 个键，
但是可以被部分填充并保存最少 k+1、最多 2k+1 个指向子节点的指针。根页可以容纳
1 到 2k 个键。之后，一个参数 l 被引入，并且任何非叶页都可以具有 l+1 个键。
其他文献，例如 [GRAEFE11]，则描述了可以容纳多达 N 个
分隔键
和 N+1 个
指针
的节
点，这些节点具有类似的语义和不变式。
这两种方法给我们带来了相同的结果，而其间的差异仅用于强调每篇文献的内容有所不
同。在本书中，为了清楚起见，我们坚持使用 N 作为键的数目（对于叶节点则是键值对
的数目）。
2.3.6 B
树的节点分裂
要将一个值插入 B 树，我们首先必须定位目标叶节点并找到插入点。为此，我们使用
前面小节中描述的算法先进行查找操作。在定位叶节点之后，键和值被追加到叶节点之
上。在 B 树中，更新操作则通过使用查找算法定位目标叶节点并将新值与现有键相关联
来完成。
如果目标节点没有足够的可用空间，我们就说该节点
溢出
（overflow）了 [NICHOLS66]，
此时必须将其分裂为两部分才能放入新的数据。更准确地说，如果以下条件成立，则需
要分裂节点：
•
对于叶节点：如果节点最多可以容纳 N 个键值对，且再插入一个键值对将使其
超过
其最大容量 N。
•
对于非叶节点：如果节点最多可以容纳 N
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.