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
树的实现
｜
65
单元格指针
单元格
图
4-7
：带间接指针的二分搜索（要搜索的元素显示为灰色。虚线箭头表示通过单元格指针进
行二分搜索。实线表示跟随单元格指针所进行的访问动作，这是比较单元格的值与搜索键所必
需的动作）
4.3
传播分裂与合并
正如我们在前几章中讨论过的，B 树的分裂与合并可以传播到更高的层。为此，我们需
要一条从将要分裂或合并的叶节点遍历回根节点的路径。
B 树节点可以包含父节点指针。由于在通过较高层的页引用较低层的页时，一定会触发
页换入，所以我们甚至没有必要将这些信息保存在磁盘上
译注 1
。
就像同级指针（参见 4.1.2 节）一样，每当父节点发生变化，父节点指针就必须更新。当
带有页标识符的分隔符键从一个节点转移到另一个节点时，比如父节点分裂、合并或再
平衡时，都需要进行此更新。
一些实现（例如 WiredTiger）将父指针用于叶节点的遍历以避免死锁，死锁可能在使用
同级指针时发生（参见 [MILLER78]、[LEHMAN81]）。该算法不使用同级指针遍历叶节
点，而是使用父指针，就像我们在图 4-1 中看到的那样。
要寻址和定位同级节点，我们可以递归地跟随父节点的指针。此时，搜索就会递归地向
上继续，最终到达根节点，并继续向下返回到叶子层。
导航信息
如果不存储和维护父节点指针，则我们还可以跟踪在遍历目标叶节点路径上的节点，并
在发生级联分裂（插入时）或合并（删除时）的情况下，以相反的顺序跟踪父节点链路。
译注 1：而是在换入时维护父节点指针。
66
｜
第
4
章
在进行可能导致 B 树结构变化的操作（ ...
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.