Как базы данных работают с таблицами данных, которые не помещаются в памяти?

Question

Предположим, у вас действительно большая таблица, скажем, несколько миллиардов неупорядоченных строк, и теперь вы хотите проиндексировать ее для быстрого поиска. Или, может быть, вы собираетесь загрузить его и заказать его на диске с кластерным индексом. Очевидно, что когда вы получаете количество данных такого размера, вы должны прекратить предполагать, что вы можете выполнять такие вещи, как сортировка в памяти (ну, не без перехода к виртуальной памяти и значительного снижения производительности).

Может кто-нибудь подсказать, как базы данных обрабатывают такие большие объемы данных, как эта? Я предполагаю, что есть алгоритмы, которые используют некоторую форму кеширования смарт-дисков для обработки всех данных, но я не знаю, с чего начать. Ссылки будут особенно приветствоваться. Может быть, учебник по продвинутым базам данных?

Answer 1

Multiway Merge Sort - ключевое слово для сортировки огромных объемов памяти

Answer 2

Насколько я знаю, в большинстве индексов используется некая форма B-деревьев , которой не нужно хранить какие-либо данные в памяти. Вы можете просто поместить узлы дерева в файл, а затем перейти к положению переменных в файле. Это также можно использовать для сортировки.

Answer 3

Вам придется каким-то образом разделить ваш набор данных. Разложите каждый раздел в ОЗУ отдельного сервера. Если бы у меня был миллиард 32-битных int - это 32 ГБ оперативной памяти. И это только ваш индекс.

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

Answer 4

Хм ... Интересный вопрос.

Я думаю, что наиболее часто используемые системы управления базами данных используют механизм операционной системы для управления памятью, а когда физическая память заканчивается, таблицы памяти переставляются.

Answer 5

Вы создаете движок базы данных?

Редактировать: Я создал систему баз данных на основе дисков еще в середине 90-х годов.

С записями фиксированного размера проще всего работать, потому что смещение вашего файла для определения местоположения записи может быть легко рассчитано как кратное размеру записи. У меня также были некоторые записи с переменным размером записи.

Моя система должна быть оптимизирована для чтения. Данные фактически сохранялись на CD-ROM, поэтому они были доступны только для чтения. Я создал двоичные файлы дерева поиска для каждого столбца, в котором я хотел искать. Я взял реализацию дерева двоичного поиска с открытым исходным кодом в памяти и преобразовал ее для произвольного доступа к файлу диска. Упорядоченные операции чтения из каждого индексного файла были простыми, а затем считывание каждой записи данных из основного файла данных в соответствии с порядком индексации также было простым. Мне не нужно было выполнять какую-либо сортировку в памяти, и система работала намного быстрее, чем любая из доступных систем СУБД, которая в то время работала на клиентском компьютере.

Для данных фиксированного размера записи индекс может просто отслеживать номер записи. Для записей данных переменной длины в индексе нужно просто сохранить смещение в файле, с которого начинается запись, и каждая запись должна начинаться со структуры, которая определяет ее длину.