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.
B
树的实现
｜
67
4.4
再平衡
一些 B 树的实现方案试图推迟分裂和合并操作，以便通过在层内
再平衡
各元素来平摊代
价，或将元素从占用较多的节点转移到占用较少的节点中，通过这一方式尽可能推迟分裂
或合并。虽然维护代价可能更高一些，但这有助于提高节点利用率以及减少树的层数。
我们可以在插入和删除操作期间执行负载平衡 [GRAEFE11]。为了提高空间利用率，我
们并不在溢出时拆分节点，而是可以将一些元素转换到同级的另一个节点中，并为插入
腾出空间。类似地，在删除过程中，我们可以选择从相邻节点中移动一些元素，而不是
合并同级节点，以确保节点至少是半满的。
B* 树持续在相邻节点之间分发数据，直到两个同级节点都已满 [KNUTH98]。另外，该
算法不是将单个节点拆分为两个半空节点，而是将两个节点拆分为三个节点，每个节点
是三分之二满的。SQLite 在实现中使用此变体。这种方法通过推迟分裂来提高平均占用
率，但需要额外的跟踪和平衡逻辑。而更高的利用率也意味着更高效的搜索，因为树的
高度更低，通往被搜索叶节点的路径上的页也更少。
图 4-9 展示了相邻节点之间的元素分布，其中左侧同级节点包含的元素多于右侧节点。
来自占用率较高的节点的元素被移动到占用率较低的节点。平衡的过程也改变了同级节
点的最小 / 最大不变量，我们必须相应地更新父节点的键和指针。
平衡前 平衡后
图
4-9
：
B
树的再平衡
—
在占用率较高的节点和占用率较低的节点之间分配元素
负载平衡是许多数据库实现中运用的一种有用技术。例如，SQLite 实现了
同级节点平 ...
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.