Структура файлов БД.

Нужен совсем простой вариант какой-либо NoSQL базульки с ключем типа «строка» и данными типа «строка».

пиши json в файл в одном потоке --- вот тебе и nosql

http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf http://citforum.ru/database/articles/bst/ http://citforum.ru/database/articles/b-tree_indexes/ http://citforum.ru/database/digest/over001.shtml

Серёга, насчёт машинного поиска - это к Кнуту. Кнут, конечно, сложен в освоении, поэтому ищи его клонов из тех, кто попроще. Прямо сейчас не назову, слегка оторвался от тренда.

Спасибо. Многое из этих данных уже читал. Первая ссылка - интересно, почитаю.

Rastafarra один большой json не вариант. А ну как данных под терабайт.

rht Да с поиском (и вообще работой с деревьями) в принципе трудностей нет. Меня интересует как все это в файл забить, как его организовать. Где обычно список блоков хранят, как хранят и тд...

http://www.nobius.org/~dbg/practical-file-system-design.pdf

http://citforum.ru/database/articles/bst/

Чо-то они там слишком уж навертели. Radix tree во внешней памяти не сильно сложно делать. Но возни много, да. Я делал для своих велосипедов key-value хранилище с транзакциями https://github.com/vmxdev/tkvdb . Так и не доделал. Хотя там осталось немного - допилить корректное удаление ключей и vacuum. Ну, может как-нибудь соберусь с силами, домучаю.

Идея очень простая - в заголовке файла есть указатель на текущий корень дерева. Транзакция в памяти строит новое маленькое дерево обновлений (получается такой diff по отношению к БД), при коммите это дерево дописывается к файлу и обновляется указатель на корень. То есть файл состоит из небольших кусков-«транзакций», и это что-то вроде append-only database.

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

B-tree (и LSM, конечно) делают по-другому. Вот BDB и SQLite кстати пишут в отдельные файлы при коммите. Непонятно, может в этом есть какой-то смысл

В простых движках обычно нет ничего, кроме B+ tree. Т.е. Каждая таблица является index organized по «главному» ключу. Дополнительные индексы являются также деревьями по дополнительному ключу, но вместо данных содержат значение главного ключа.

Сейчас наверное самый горячий транзакционный движок это lmdb. Он использует блоки фиксированного размера как и любой B tree, и copy on write для concurrency и transaction integrity.

Ага, посмотрю. Кстати скажи, если ключ будет длиной в 64к, сколько места будет занимать такая база с одним ключом? База с trie я имею ввиду. Я чот думал, что такой способ хорошо, когда ключи небольшие. Ну например какой-то хеш.

Да я про это же. Но затолкать btree с фиксированным значением длины ключей в файл довольно просто, а вот как быть, если ключи имеют разную длину (от 1 до +∞)? строки например.

Но в общем вон там анонимус много ссылок понакидал, читаю. Мож что пойму =)

если ключ будет длиной в 64к, сколько места будет занимать такая база с одним ключом?

Ну 64к и будет (+всякие заголовки). Это не просто trie, а radix trie, в википедии хорошо расписано: https://en.wikipedia.org/wiki/Radix_tree

В узле хранится префикс и ссылки на хвосты, если дерево разветвляется.

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

Практически все немного сложнее. Вот в моей реализации для каждой транзакции нужно копировать как минимум корневой узел + добавляющиеся (и обновляющиеся) данные. В худшем случае (если существуют все 256 дочерних узлов) корневой узел получится 8*256=2к (8 байт - размер «указателя» на дочерний узел). То есть размер зависит от количества уже существующих данных, и для экономии диска эффективнее писать в одну транзакцию как можно больше данных.