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.
124
｜
第
7
章
7.1.4
合并迭代
由于磁盘驻留表上的内容是经过排序的，所以我们可以使用多路归并排序算法。例如，
我们有三个数据源：两个磁盘驻留表和一个 memtable。通常，存储引擎提供
游标
或
迭代
器
来遍历文件内容。此游标保存上次消耗的数据记录的偏移量，可以用来检查迭代是否
完成，也可以用于抽取下一个数据记录。
多路归并排序使用一个
优先级队列
，如
最小堆
（min-heap）[SEDGEWICK11]，该队列最
多保存 N 个元素（其中 N 是迭代器的数目），该队列对其内容进行排序并准备返回的下一
个最小的元素。每个迭代器的头被放入队列。队列头部的元素就是所有迭代器的最小值。
优先队列是一种数据结构，用于维护一个有序数据项队列。当常规队列按照
添加的顺序（先进先出）保留项目时，优先级队列在插入数据项时进行重新排
序，具有最高（或最低）优先级的数据项被放在队列的头部。这对于合并迭代
特别有用，因为我们必须有序地输出元素。
当从队列中移除最小的元素时，检查与之相关联的迭代器是否有下一个值，然后将该值
放入队列，队列将被重新排序以维持顺序。
因为所有迭代器中的内容都是有序的，所以从之前的最小元素对应的迭代器取出下一个
值并插入优先队列也维持了一个不变式
—
队列仍然包含来自所有迭代器的最小元素。
每当其中一个迭代器耗尽时，就不再插入这个迭代器的值，但是算法仍然继续执行。该
算法持续执行到查询条件被满足或所有迭代器耗尽为止。
图 7-5 展示了上述合并过程的一个示意图：头部元素（源表中的浅灰色项）被放置到优
先级队列中。优先级队列中的元素返回输出迭代器。所产生的输出是有序的。 ...
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.