Внутреннее устройство баз данных

В общем, смысл в том, что мне нужно сделать свою базу данных, не используюя стандартные движки
База данных должна включать в себя неограниченное (теоретически... на самом деле 2^32 вполне хватит ) число записей, каждая из которых может иметь несколько подзаписей (а те, в свою очередь, ещё несколько подзаписей и т.д), т.е. иметь вложенную структуру. Поддержка перекрёстных ссылок (т.е. несколько ссылок на одну запись) приветствуется, хотя необязательна. Запись - это одно или несколько полей (чаще всего как минимум два: заголовок и данные) переменной неограниченной длины, часть из которых может быть зашифрована (ну, это уже детали).
Требования: быстрый (а ещё лучше - мгновенный) поиск (желательно по любому полю), чтение, изменение, добавление и удаление записи вне зависимости от размера самой базы данных с минимальным "мусором" (имеются в виду различные вспомогательные данные, индексирование и т.д). Быстрая сортировка по какому-либо полю из БД тоже приветствуется, хотя для этих целей её можно и пересоздать
Так вот, я бы хотел узнать, как устроены современные базы данных (внутри) или услышать какие-нибудь интересные идеи по этому поводу. Организовать быстрый поиск и чтение - это задача не сложная, а вот когда добавляется редактирование, то тут возникают проблемы. Представьте себе: база данных на несколько мегабайт, при этом нужно отредактировать самую первую запись и без тормозов.
- Заранее спасибо!

Цитата

Jin X, 8.08.04, 16:34
а вот когда добавляется редактирование, то тут возникают проблемы.

Без проблем ведь структура известна (и постоянна). Тоесть есть N полей с размером К байт что бы перейти к записи О нада передвинуться на (N-O)*K байт, или от начала О*К.

Цитата

Jin X, 8.08.04, 16:34
Быстрая сортировка по какому-либо полю из БД тоже приветствуется, хотя для этих целей её можно и пересоздать

Без сортировки современные БД и не работают.

Jin X- задада не из легких. Inter Base - открытая архитектура и инфы много. DBF- тебе наверное не подойдет.

Я бы посоветовал начать с Дейта. Там отлично описаны все принципы...

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

Цитата tserega,9.08.04, 04:57

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

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

Товарища Кнута почитать надо бы
и с деревьями ознакомиться

В общем случае разработать темплейный класс..

Сообщение отредактировано: ms - 09.08.04, 10:14

Цитата

Bas, 9.08.04, 11:40
Без проблем ведь структура известна (и постоянна). Тоесть есть N полей с размером К байт что бы перейти к записи О нада передвинуться на (N-O)*K байт, или от начала О*К.

Проблема в том, что K неизвестно и может меняться. Даже если K - это указатель, то как хранить сами строки, чтобы их было легко редактировать? Т.е, упрощённо говоря, представь себе, что нужно сделать что-то типа текстового редактора, где каждая строка может быть любой длины, но к каждой должен быть мгновенный доступ, зная первые буквы. Причём, этот редактор вовсе не обязан держать весь файл в памяти.

Вообще говоря, я не хочу использовать готовые БД потому, что прога не очень большая, а тащить в дистрибутив ещё мега 3-4 из-за движка типа BDE не хочется. Ведь даже Access стоит не у каждого. Если это действительно сложная задача, то видимо, придётся держать весь файл в памяти, но тогда есть опасность того, что данные потеряются, например, при зависании компа. А периодически записывать весь файл - это лишнее время. К тому же, только пустая БД, например, Access'а занимает больше 50kb

Для таких вещей уже давно придуманы embedded databases. Неужели 3-4 мега стоят 2-3 месяцев работы по изобретанию велосипеда?

Мне не нужна громадная система, которую нужно строить 2-3 месяца. Вполне пойдёт что-нибудь попроще, что можно сделать за пару дней. К тому же, эти 3 мега придётся пихать во все проги, которые используют БД.

БД с записями переменной длины, ?

Ты намекаешь на XML?

Не подходит?

Да я пока как-то и не разбирался с ним.
Если работает быстро и туда можно запихнуть любые символы (т.е. и табы, и пробелы в начале/конце строк, и "управляющие" и т.д), то может и подойти
Спасибо

Добавлено в 09.08.04, 17:14:
В Delphi даже стандартные компоненты есть для XML

Запихнуть можно любые. (см. например конструкцию CDATA а также Entities).
То что компоненты есть - это конечно круто (еще нехватало чтобы их не было), только как быть с требованием что файл на несколько мегов а тебе надо быстро искать и редактировать?
Я вот например столкнулся что реализация XPath (язык запросов к хмл) Engine может быть весьма неэффективной..

Эх! Если XML работает так же быстро, как чтение и перезапись всего файла, тогда он мне нафиг не нужен.

Что значит ХМЛ работает/не работает?? ХМЛ это язык он не может "работать". Есть реализация конкретных парсеров, ктр может работать быстро, медленно или вообще не работать.
Суть в том, что тебе придется все держать в памяти в виде DOM-объекта. Тогда есть шанс что при не очень большом файле и толковой реализации XPath'a ты сможешь быстро обновить элемент.
Но все это неправильно, имхо.

Если в памяти, то я и без XML'я смогу.
А если вдруг внезапно питание обрывается, то что происходит? Всё падает?

Я о том и говорю, что сможешь. При всей моей любви к ХМЛ - не надо скрещивать бобика со свиньей. ХМЛ - средство ПРЕДСТАВЛЕНИЯ данных, а отнюдь не их хранения.
Насчет отключения питания - тебе нужны контрольные точки во времени, чтобы сохранять состояние на диске. Кроме этого, субд имеют еще массу тонкостей (правда, тебе похоже поддержка конкурентного доступа к данным не нужна). Поэтому я тебе и сказал, что нужно определиться - либо пользуй нормальный движок (т.е. юзеры расплачиваются мегабайтами за надежность и согласованность хранения), либо пиши обыкновенный файл и никому ничего не гарантируй.
То что ты говоришь "простенькую СУБД за 2-3 дня" - извини меня. То что можно написать за считанные дни СУБД являться не будет никогда (всего лишь мое мнение).

Цитата

kl, 10.08.04, 00:45
правда, тебе похоже поддержка конкурентного доступа к данным не нужна

Это точно

Цитата

kl, 10.08.04, 00:45
То что можно написать за считанные дни СУБД являться не будет никогда

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

Цитата

kl, 10.08.04, 00:45
либо пиши обыкновенный файл и никому ничего не гарантируй.

Дык, а как его писать. Какую структуру использовать? Каждую минуту перезаписывать весь файл? Ну это ж дибилизм!

На самом деле, конечно, больше мега этот файл у большинства юзеров будет едва ли, но нужно рассчитывать на самое худшее

Конечно дебилизм. Но тебе уже не один раз сказали, что единственный способ от этого избавиться - индексирование. Только про 2-3 дня можешь смело забыть.
Есть 2 основных подхода:
1. Значения ключей ассоциированы с адресом строки в файле. Сами записи - неупорядочены. Реализация - В*-дерево.
2. Адрес строки есть функция от ключевых атрибутов. Строки более-менее упорядочены (ну до страниц конечно). Тут придется помучаться с резервированием места и т.д. Подходит для не очень часто обновляющихся таблиц. Реализация - кластерные хеш-индексы.
Если не хочешь перезаписывать файл - читай и разбирайся.. мы в меру сил поможем.

Под Windows проблема вполне решаема путем использования MapViewOfFile. Скорость работы вполне сопоставима со скоростью работы виртуальной памяти. При внесении изменеий сохраняются на диск только измененные страницы, а не весь файл. К минусам можно отнести время инициализации больших файлов. К примеру, файл в 1 крокодил (GB) мапируется заметное время при инициализации.
В моей практике клиенты файлы больше, чем крокодил не генерили, максимально было около 800 МВ, хотя теоретически размер файла ограничен размером своп пространства, и на сервере может достигать 2^34. Подобная методика позволяет действительно за несколько дней выпустить работоспособную версию. Естественно, к классическим СУБД такая методика не имеет никакого отношения.

Просто файл не пойдёт. Чтобы защититься от сбоев, нужны механизмы, аналогичные Commit / Rollback. То есть, грубо говоря, сначала пишешь новые данные куда-нибудь в файл, не затирая при этом старые данные, потом FlushFileBuffers(), потом изменяешь некоторый (короткий) указатель со старых данных на свежезаписанные, и потом снова FlushFileBuffers(). Тогда сбои не нарушат целостность базы данных.

Laco, просто замечание: размер файла ограничен лишь размером доступного виртуального адресного пространства. А это как правило гораздо больше чем оперативка + swap + размер жесткого диска. Читал что даже на 32 битных архитектурах он 64 Tb! Правда реально адресоваться к 4 Gb или 16 Gb (Pentium Pro+).

Jin X, СУБД даже со всеми послаблениями, которые ты допускаешь, написать в одиночку даже за 2 недели НЕВОЗМОЖНО. Я только в позапрошлом семестре проходил все это: индексы, первичные ключи, алгоритмы отката, коллизии доступа и прочее.
И что ты подразумеваешь под "БД размерами 3-4 Mb"? Ты что, сервер базы данных собираешься дополнительно поставлять? Брось, ты на это в большинстве случаев даже прав не имеешь. Твоя задача - написать клиента БД, который может использовать любую БД по выбору пользователя. Так почему бы тебе не обратить внимание на ODBC? Единообразный доступ к любым базам данных, а уж какая пользователю понравиться - его личное дело, и тебе хорошо -- ничего лишнего поставлять не надо. Правда есть недостаток: перед использованием проги надо сначала произвести какие-то пассы с драйверами ODBC, но может быть это автоматизируется... Кроме того, ODBC вроде как является стандартом и существует во всех версиях Windows, начиная, по-моему, с Win95, и в Unix. Так что это то, что тебе действительно нужно. К сожалению про ODBC знаю немного, даже ссылок приличных дать не могу. Попробуй посмотреть отсюда www.odbc.org.
Good luck!

Jin X wrote:

Цитата

Вообще говоря, я не хочу использовать готовые БД потому, что прога не очень большая, а тащить в дистрибутив ещё мега 3-4 из-за движка типа BDE не хочется. Ведь даже Access стоит не у каждого.

По-моему начиная с NT4.0 / 98 в составе винды имеются ODBC-шки для работы с access.mdb, dBase.dbf, paradox.db итд. И ничё с собой таскать и устанавливать не надо, если будешь работать с БД через ОДБЦ.

Цитата

К тому же, только пустая БД, например, Access'а занимает больше 50kb

Это если ты создашь её с помощью office\msaccess.exe...
а если своей прогой via odbc, будет 10кб %)

насчет быстрого изменения-можно сделать так (по-моему, так сделано в стандартных перловских базах):

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

2)можно же сделать просто такую вещь: для каждой записи есть флаг действительна она или нет. изменение-это сброс флага у изменяемой записи и дописывание новых данных в конец. так же как и в предыдущем способе удаление ненужных данных- периодическое (например, каждые n обращений к функции изменения)

эти способы должны подойти если тебе нужна быстрая база из-за частых обращений к ней