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.
108
｜
第
6
章
许我们连接多个有序段，并减少在其中搜索的成本。
6.4.2
对数级的有序段
FD 树结合了分段级联与创建
对数级的有序段
：一组不可变的排序数组，它们的大小以
系数 k 递增，并且它们是通过将上一个层与当前层合并而创建的。
最高层的有序段是在头部树变满的时候创建的：其叶子的内容被写入第一层。一旦头部
树再次填满，它的内容将与第一层项合并。合并后的结果将替换第一个有序段。当较高
层有序段的长度达到阈值时，会创建较低层有序段。如果已存在较低层的有序段，则将
其替换为与较高层有序段的内容合并后的结果。这个过程与 LSM 树中的压缩相当类似，
在 LSM 树中，不可变的表内容被合并以创建更大的表。
图 6-6 展示了一个 FD 树的示意图，其包括顶部的一个头部 B 树、两个对数有序段 L1
和 L2，以及它们之间的桥。
头部 B 树
有序段
L1
有序段
L2
图
6-6
：
FD
树概览示意图
为了使所有有序段中的项都可寻址，FD 树使用了一种修改版的分段级联，其中来自较
低层页的
头元素
被传播为指向较高层的指针。通过使用这些指针，其降低了在较低层树
中搜索的成本，因为搜索已经在较高层上部分完成，从而可以从最接近的匹配继续。
由于 FD 树不在原地更新页，并且可能在几个层上存在相同键的数据记录，所以 FD 树
通过插入墓碑（tombstone，FD 树的论文中将其称为
过滤器条目
）来进行删除。该墓碑
指示与相应键相关联的数据记录已被删除，必须丢弃较低层中该键的所有数据记录。当
墓碑一直传播到最低层时，它们便可以被丢弃了，因为此时可以保证已经没有需要它们 ...
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.