поддержание отсортированного списка, который больше, чем память

Question

У меня есть список кортежей.

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

При увеличении количества

 "Alice" += 2

порядок должен быть сохранен:

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

Когда все в памяти, есть довольно простые способы (некоторые более или менее), чтобы эффективно реализовать это. (с использованием индекса, вставки и т.д.)

Дополнительный вопрос: что, если даже индекс не помещается в память?

Как бы вы подошли к этому?

Answer 1

B + деревья заказать количество предметов с помощью ключа. В этом случае ключ - это число, а элемент - имя человека. Все дерево B + не нужно помещать в память - только текущий узел, который ищется. Вы можете установить максимальный размер узлов (и косвенно глубину дерева), чтобы узел помещался в памяти. (На практике узлы обычно намного меньше, чем объем памяти.)

Элементы данных хранятся на листьях дерева, в так называемых блоках. Вы можете хранить элементы, встроенные в индекс, или сохранять указатели на внешнее хранилище. Если данные имеют регулярный размер, это может обеспечить эффективный поиск из файлов. В примере с вопросом элементы данных могут быть отдельными именами, но было бы более эффективно хранить блоки имен, причем все имена в блоке имеют одинаковое количество. Имена в каждом блоке также могут быть отсортированы. (Имена в самих блоках могут быть организованы как B-дерево.)

Если количество имен становится достаточно большим, чтобы блоки дерева B + становились чрезмерно большими, ключ можно превратить в составной ключ, например, (считать, первая буква). При поиске в дереве необходимо сравнивать только количество, чтобы найти все имена с этим количеством. При вставке или поиске определенного имени с заданным количеством можно сравнить полный ключ и включить фильтрацию по префиксу имени.

В качестве альтернативы, вместо составного ключа элементы данных могут указывать на смещения / блоки во внешнем файле, который содержит блоки имен, что будет поддерживать само дерево B + небольшим.

Если блоки btree связаны друг с другом, запросы диапазона могут быть эффективно реализованы путем поиска начала диапазона, а затем следуя указателям блоков на следующий блок, пока не будет достигнут конец диапазона. Это позволит вам эффективно реализовать «найти все имена с количеством от 10 до 20».

Как отмечалось в других ответах, СУБД - это предварительно упакованный способ хранения списков, которые не помещаются в память, но я надеюсь, что это дает представление о структурах, используемых для решения проблемы.

Answer 2

Реляционная база данных, такая как 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 <code>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 3

То, что вам нужно, это из основных алгоритмов для контейнерных классов, в частности, из контейнерного класса из основного списка. Посмотрите библиотеку stxxl , где вы найдете несколько замечательных примеров из основных алгоритмов и обработки.

Вы также можете посмотреть этот связанный вопрос

Answer 4

Интересный подход, совершенно не похожий на BTrees, - Judy Tree

Answer 5

Читайте о B-деревьях и B + -деревьях. С их помощью индекс всегда можно сделать достаточно маленьким, чтобы поместиться в память.

Answer 6

RDMS? Даже плоские версии файлов, такие как SQLite. В противном случае комбинация, использующая ленивую загрузку. Храните только X записей в памяти, самые верхние записи Y и самые последние Z, которые обновили счет. В противном случае таблица столбцов Key, Count, в которой вы запускаете UPDATE, изменяет значения. Упорядоченный список можно получить с помощью простого SELECT ORDER BY.

Answer 7

Вы не указываете, что вам нужно добавлять или удалять какие-либо элементы из списка, просто сохраняйте его отсортированным.

Если это так, простой плоский файл подход - обычно для удобства используется mmap - будет работать и будет быстрее, чем более общая база данных.

Вы можете использовать bsearch для определения местоположения элемента или сохранения набора значений слотов для каждого значения.

Когда вы получаете доступ к элементу, то и к части файла, в которой он находится (представьте в терминах страниц памяти') ОС автоматически считывает данные в ОЗУ, а слот и смежные слоты даже копируются в строку кэша L1.

Вы можете сразу же сравнить соседние слоты, чтобы увидеть, увеличивается ли значение илиуменьшение приводит к тому, что элемент выходит из строя;если это так, вы можете использовать линейную итерацию (возможно, дополненную bsearch), чтобы найти первый / последний элемент с соответствующим количеством, а затем swap их.

Управление файламиэто то, для чего создана ОС.

Answer 8

Конечно, я знаю, что могу использовать базу данных. Этот вопрос был больше о деталях реализации, решающих это «вручную»

Итак, по сути, вы спрашиваете «Как база данных делает это?» На что ответ, он использует дерево (как для данных, так и для индекса) и хранит только часть дерево в памяти в любое время.

Как уже упоминалось, B-деревья особенно полезны для этого: поскольку жесткие диски всегда читают фиксированное количество за раз ( "размер сектора" ), Вы можете сделать каждый узел размером сектора, чтобы максимизировать эффективность.

Answer 9

Что касается «деталей реализации, решающих эту проблему« вручную »», вы можете прочитать о том, как системы баз данных делают это, выполнив поиск оригинальных работ по проектированию баз данных или заметок для выпускников курса по архитектуре баз данных.

Я провел некоторый поиск и нашел обзорную статью Дж. Грефа под названием " Методы оценки запросов для больших баз данных ". Это несколько исчерпывающе охватывает каждый аспект запросов больших баз данных, но весь раздел 4 посвящен тому, как «системы оценки запросов ... получают доступ к базовым данным, хранящимся в базе данных». Кроме того, опрос Graefe был связан со страницей курса для CPS 216: Расширенные системы баз данных в Duke, осень 2001 года. Неделя 5 была на Физическая организация данных , которая говорит, что большинство коммерческих СУБД организуют данные на диске с использованием блоков в N-арной модели хранения (NSM): записи хранятся в начале каждого блока, а в конце существует «каталог».

Смотри также:

• Примечания к лекции CPS 216, весна 2004 г.
• MIT OCW 6,830 Системы баз данных