Comments 31
Я может чего-то не понимаю, но B+Tree нужно для индексов в СУБД. То есть когда у вас есть не просто поиск по ключу, а поиск по произвольному предикату и вы хотите этот поиск ускорить.
Для поиска по ключу подойдет просто хранение в виде файлов на диске: ключ - имя файла, значение - содержимое.
Да, можно на индексе самой файловой системы, но тут же вся соль в "реализации с нуля". Boson хоть и игрушечная, но всё таки СУБД. И в ней будет настоящий B+ Tree индекс с бинарным поиском в узлах, чтобы достичь сложности O(log2 t logt n). Пока реализация будет только для ID, но тот же механизм может быть применён и по другим полям документов в будущем.
Вам намекают что от первичного ключа ожидается поведение O(1) - на то он и первичный и никакие b-tree этого не дадут
Не надо додумывать. Во всех базах обращение по ключу - O(logN) по большом основанию, если данные не находятся в памяти. В NTFS или ReFS индекс файлов в папке это тоже btree, поэтому там также будет O(logN).
Во всех материалах где читал про бд - первичный ключ мапится напрямую на место хранения на диске, и именно по этому первичный ключ всегда только один. Это близко к О(1) и очень далеко от других метрик. Или вы счтаете что обращение к файлу по известному отступу это не О(1)?
Только после того как вы по индексу нашли где запись.
первичный ключ мапится напрямую на место хранения на диске, и именно по этому первичный ключ всегда только один
вот смотрите, у вас первичный ключ по id. в базе миллиард записей с id от 1 до 10'000'000'000.
как вы предлагаете с O(1) найти, скажем, запись с id=3'456'789'012?
File.Seek(id×recordSize)
Record=File.Read(recordSize)
в базе миллиард записей с id от 1 до 10'000'000'000
Это какраз к разработчику бд и вопрос. Насколько я знаю делается несколько уровней хеш таблиц с адресами участков. Но даже в моем случае проблемы нет ) формально я могу хранить пустые значения на диске.
формально я могу хранить пустые значения на диске.
хорошо, немного усложним задачу: первичный индекс по полю, хранящему uuid v4 (128-битное число, в котором 122 бит случайны)
плохой выбор - антипатерн для большинства БД
Сортировка такого поля смысла не делает - значит первичным ключом (в смысле адреса хранения) должно быть другое поле - это покрываем обычным индексом
btw, вы путаете первичный ключ и кластерный индекс.
но кластерный индекс (как минимум в mssql и mysql) это обычно то же дерево, что и прочие индексы. просто он хранит в себе все прочие поля таблицы.
P. S. использование uuid в качестве первичного ключа никакой не антипаттерн, а обычная практика. да, есть связанные с этим проблемы с производительностью, по этому поводу придуманы ulid и новый uuid
Хорошее начало.
Как предлагаете удалять записи?
Что делать если записи переменой длины?
Что делать если ключ не равномерно возрастающий?
Амортизированный O(1) на поиск могут дать только хэш мапы, но думаю с подобным подходом другие проблемы.
разумеется, там есть другие проблемы.
во-первых, O(1) — лукавство. размер хэш-таблицы приходится увеличивать с ростом базы, время поиска в таблице на 100 записей и на 10 миллиардов записей будет совершенно разное — в первом случае хэш-таблица поместится в кэше процессора, во втором за ней придётся обращаться к накопителю (а то и к другой ноде).
да и про коллизии не надо забывать, из-за них O(1) — это лучший случай.
во-вторых, в реальной жизни часто нужен не только поиск по точному значению, b-tree же позволяет искать по интервалу и подобное.
Так и b-tree тоже не в памяти, c хэш-мапами плохо что они не дают локальность рядом расположенные значений. O(1) это не лучший случай, а средний(амортизированный), и он вполне гарантирован если в таблице поддерживается разумный load factor.
Так и b-tree тоже не в памяти
разумеется. но там никто O(1) не обещает.
O(1) это не лучший случай, а средний(амортизированный), и он вполне гарантирован если в таблице поддерживается разумный load factor
а худший? разве есть способ, позволяющий поддерживать для произвольных входных данных отстутствие множественных коллизий без раздувания хэш-таблицы?
Худший O(n), но в реальности это возможно только, если произвести целенаправленную атаку на хэш функцию. Если рассматривать это с вероятностной или практической точки зрения, то она бесконечно мала.
Не очень понял, что значит "раздувание", вам в любом случаи надо где-то хранить ключи и значения, обычно считают что при load factor <= 0.7, коллизий достаточно мало, и в среднем сложность будет O(1).
Для поиска по ключу подойдет просто хранение в виде файлов на диске: ключ - имя файла, значение - содержимое.
Это привязка к тому же b-tree, как правило, но реализованному для конкретной файловой системы.
B+Tree нужно для индексов в СУБД
LMDB, libmdbx, BoltDB (из тех что первыми приходят в голову) построены на B+tree, т.е. это основная структура для хранения данных и обращения к ним по ключу (а не только индекс).
Дефрагментацию не будете делать?
Boson — разработка СУБД «с нуля» (часть II)