维护大于内存的排序列表

B+ trees 使用键订购多个项目。在这种情况下,键是计数,项是人名。整个B+树不需要装入内存-只需要搜索当前节点。您可以设置节点的最大大小(间接地设置树的深度),以便节点能够装入内存。(实际上,节点通常远小于内存容量。)

数据项存储在树的叶子上,即所谓的块中。可以在索引中以内联方式存储项,也可以存储指向外部存储的指针。如果数据有规律地调整大小,这可以使从文件中进行有效的检索。在问题示例中,数据项可以是单个名称,但是将名称块(所有名称)存储在具有相同计数的块中会更有效。每个块中的名称也可以排序。(块本身的名称可以组织为B树。)

如果名称的数量变得足够大,以至于B+树块变得越来越大,则可以将密钥制作成复合密钥,例如(count,first letter)。搜索树时,只需比较计数即可找到具有该计数的所有名称。当插入或搜索具有给定计数的特定名称时,可以将全键与按名称前缀包括筛选进行比较。

或者,数据项可以指向包含名称块的外部文件中的偏移量/块,而不是复合键,这将使B+树本身保持较小。

如果btree的块链接在一起,则可以通过搜索范围的开始,然后跟随块指针到下一个块,直到达到范围的结束,来有效地实现范围查询。这将使您能够有效地实现“查找计数在10到20之间的所有名称”。

正如其他答案所指出的那样,RDBMS是一种预先打包的存储列表的方法,它不适合于内存,但我希望这能深入了解用于解决问题的结构。

像mysql这样的关系数据库是专门为存储大量的数据而设计的,这些数据的总和不适合存储在内存中,查询大量的数据,甚至就地更新数据。

例如:

CREATE TABLE `people` (
    `name`    VARCHAR(255),
    `count`   INT
);

INSERT INTO `people` VALUES
('Bob', 3),
('Alice', 2),
('Jane', 1);

UPDATE `people` SET `count` = `count` + 2;

后 UPDATE 语句,查询 SELECT * FROM people ; 将展示:

+-------+-------+
| name  | count |
+-------+-------+
| Bob   |     5 |
| Alice |     4 |
| Jane  |     3 |
+-------+-------+

通过添加自动递增的主键,可以保存表中人员的顺序:

CREATE TABLE `people` (
    `id`      INT UNSIGNED NOT NULL AUTO_INCREMENT,
    `name`    VARCHAR(255),
    `count`   INT,

    PRIMARY KEY(`id`)
);

INSERT INTO `people` VALUES
(DEFAULT, 'Bob', 3),
(DEFAULT, 'Alice', 2),
(DEFAULT, 'Jane', 1);

RDMS?甚至是像sqlite这样的平面文件版本。否则是一个使用延迟加载的组合。只在内存中保留X条记录前Y条记录和Z条最近更新计数的记录。否则是一个键、计数列表,在其中运行更新,更改值。可以使用简单的select order by来检索排序列表。

了解B-树和B+树。有了这些,索引总是可以小到足以容纳内存。

与btrees非常不同的一个有趣的方法是 Judy Tree

你要找的似乎是 out of core algorithms 对于容器类,特别是核心列表容器类。退房 stxxl 图书馆为一些伟大的例子出了核心算法和处理。

你也可以看看 this 相关问题

至于“用手解决这个问题的实现细节”,您可以通过搜索数据库设计的原始论文或查找有关数据库体系结构的研究生课程笔记来了解数据库系统是如何做到这一点的。

我做了一些搜索,找到了G.Graefe写的一篇题为“的调查文章。 Query evaluation techniques for large databases “。它有点详尽地涵盖了查询大型数据库的各个方面,但整个第4节将介绍“查询评估系统…访问数据库中存储的基础数据”。此外,Graefe的调查也被链接到了CPS 216的课程页面:杜克大学的高级数据库系统,2001年秋季。第5周 Physical Data Organization 这意味着大多数商业DBMS使用N元存储模型(NSM)中的块在磁盘上组织数据:记录从每个块的开头存储,并且在末尾存在一个“目录”。

参见:

• Spring 2004 CPS 216 lecture notes
• 麻省理工学院 6.830 Database Systems

当然我知道我可以用数据库。这个问题更多的是关于“手工”解决这个问题的实施细节。

所以基本上,你是在问 “数据库是如何做到这一点的?” 对于这个问题的答案是,它使用一个树(用于数据和索引),并且在任何时候都只将树的一部分存储在内存中。

如前所述, B-Trees 特别有用:因为硬盘驱动器总是一次读取一个固定的量 “扇区大小” ,您可以使每个节点的扇区大小达到最大效率。

您不需要指定您需要添加或删除列表中的任何元素,只需将其保持排序即可。

如果是这样,一个简单的 平面文件 方法-通常使用 mmap 为了方便- 将工作 比更通用的数据库更快。

你可以使用 bsearch 定位项目,或用每个值维护一组插槽计数。

当您访问一个项目时,它所在的文件部分(以内存‘页面’的形式考虑)会被操作系统自动读取到RAM中,插槽及其相邻的插槽甚至会被复制到一级缓存线中。

您可以立即对它的相邻插槽进行比较,以查看增量或减量是否导致项目无序;如果是,则可以使用线性迭代(可能会使用 搜索 )找到具有适当计数的第一个/最后一个项目,然后 掉期 他们。

管理文件是操作系统所要做的。