维护一个比内存大的排序列表

Question

我有一个元组列表.

[
  "Bob": 3,
  "Alice": 2,
  "Jane": 1,
]

递增计数时

 "Alice" += 2

订单应该保持:

[
  "Alice": 4,
  "Bob": 3,
  "Jane": 1,
]

当所有内容都在内存中时,有效的方法(更多或更少)可以有效地实现这一点.(使用索引,插入排序等)问题是:当列表不适合内存时,最有希望的方法是什么.

奖金问题:即使指数不适合内存,该怎么办？

你会怎么做？

Answer 1

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);

Answer 2

B +树使用密钥订购许多物品.在这种情况下,键是计数,项目是人的名字.整个B +树不需要适合内存 - 只需要搜索当前节点.您可以设置节点的最大大小(以及间接树的深度),以便节点适合内存.(实际上节点通常远小于内存容量.)

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

如果名称的数量变得足够大以致B +树块变得非常大,则可以将密钥制成复合密钥,例如(计数,第一个字母).搜索树时,只需要比较计数以查找具有该计数的所有名称.当插入或搜索具有给定计数的特定名称时,可以比较完整密钥以包括按名称前缀过滤.

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

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

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