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.
126
｜
第
7
章
总结一下，创建合并迭代器必须重复以下步骤：
1. 用每个迭代器的第一项填充优先队列。
2. 从优先队列中取出最小的元素（队列头部）。
3. 从相应的迭代器取出一个值重新填入优先队列，除非该迭代器耗尽。
合并迭代器与合并有序集合的时间复杂度相同。其内存开销为 O(N)，其中 N 是迭代器
的数目。平均情况下维护迭代器头部有序集合的时间复杂度是 O(logN)[KNUTH98]。
7.1.5
协调
合并迭代只是从多个数据源合并数据的一个方面。另一个重要方面是与同一键相关联的
数据记录的
协调
和
冲突解决
。
不同的表可能持有相同键的数据记录，例如更新和删除，这时必须对它们的内容进行协
调。前例中的优先级队列的实现必须能够允许插入与相同键关联的多个值，并触发协调。
如果记录不存在，则将其插入数据库，否则更新现有的值，这种操作称为
upsert
译注 1
。在 LSM 树中，插入和更新操作是无法区分的，因为它们并不试图
在所有源中找到先前与该键相关联的数据记录并重新设置其值，所以我们可以
说在默认情况下
upsert
记录。
为了协调数据记录，我们需要了解它们中的哪一个是优先的。数据记录持有这样做所必
需的元数据，例如时间戳。我们可以通过比较时间戳来建立来自多个数据源的数据项之
间的顺序，并找出哪个更新。
被具有更高时间戳的记录所遮蔽的记录不会返回给客户端，在压实期间也不会被写入。
7.1.6 LSM
树的维护
与可变 B 树类似，LSM 树也需要维护。该过程的性质很大程度上受到这些算法所保持的
不变式的影响。
在 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.