Лучший способ разделить значения в большом плоском файле

Question

Я создаю СУБД (в основном программное обеспечение, обрабатывающее SQL-запросы) строго для удовольствия и как опыт обучения. И мне нужно знать лучший способ разделить значения и строки.

Для конфигурации таблицы я использую XML, так как это хороший способ хранения информации. Хотя это не может быть сделано со всеми вставленными строками, так как все теги xml будут занимать много памяти. Я также думал о сериализации всех объектов, представляющих базу данных (как я использую Java) для хранения данных, но я предполагаю, что это тоже займет много памяти.

Итак, единственное, что я мог придумать, это использовать разделитель значений и разделитель строк для получения минимального объема памяти. Хотя проблема с разделителями как с одиночными символами (если я использую multicharacter, я могу использовать XML), это проблемы, если этот разделитель находится в одном из значений. Поэтому я подумал, могу ли я использовать шестнадцатеричный символ без прикрепленного символа. Это существует? И если да, то это хороший подход? Одна из проблем заключается в том, что в будущем я буду запускать BLOB. Они содержат двоичные данные и могут содержать мой разделитель значений. Какое это лучшее решение?

Скажите, что вы думаете! Я открыт для обсуждения. Кроме того, если кто-нибудь знает, как MySQL (или какой-либо другой широко используемый механизм SQL) хранит данные, это может быть интересно.

Новая идея, которую я получил

Что делать, если вы можете прочитать всю таблицу в TreeSet загружены с различными компараторами на основе того, что вы ищете в/заказ на. Тогда поиск будет одинаково быстрым, что бы вы ни искали. Недостатком этого является, конечно, что весь файл должен быть записан в объекты, которые помещены в TreeSet, может быть много ОЗУ. Как вы думаете?

Answer 1

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

• Если строки имеют фиксированную длину (зависит от определения данных таблицы), вы могли бы фиксированные смещения от записи к записи, а также среди колонн.

• Если длина записи различна, у вас будет возможность обрабатывать столбцы с фиксированной длиной, как описано выше. Для динамически значимых полей может быть ссылка на фиксированный размер (значение смещения) на другой раздел в файле, содержащий значения динамического размера. Нулевую ссылку можно рассматривать как NULL, так как ваш файл, скорее всего, будет иметь заголовок.

• Другой вариант - поддерживать индекс строки с отдельными смещениями для данных строки, возможно с зернистостью 2^N (пейджинг). Смещения должны совпадать с выравниванием фактических данных, особенно если карта отображает файл в памяти. Для начала этот индекс может быть простым, упорядоченным списком для двоичных поисков, может быть, в отдельном файле. Однако для этого потребуются некоторые разделители столбцов, как вы заявили. Я бы пошел с какой-то кодировкой длины поля, так как он не требует специальной обработки (например, экранирования) фактического содержимого поля. Вероятно, было бы эффективным поддерживать длины полей в другой структуре, которая отображается или непосредственно внедряется в этот индекс (поскольку число динамических столбцов фиксировано). Отрицательная длина поля также может обозначать значение NULL.

• Вы можете ознакомиться с реализацией sqlite для идей, так как у него очень компактный макет хранилища.