https://stackoverflow.com/questions/40740752/how-to-lay-out-b-tree-data-on-disk

Гуглите «b+tree как ее хранить и модифицировать на диске»

Прежде чем начинать столь сурьёзный проект, рекомендуется прочитать от корки до корки: Garcia-Molina «Database Systems - The Complete Book» (2ed, 2008). Там целый раздел посвящён имплементации – в т.ч. нужные тебе on-disk structures.

А если тебя интересует NoSQL и т.п. (т.е. чё-нить попроще полновесного SQL-сервера), то – DDIA, там достаточно подробно обсуждаются различные компромиссы. Хотя:

(1) On-disk structures – всё равно придётся читать первую книгу.

(2) DDIA даёт общий взгляд и содержит огромное количество ссылок на различные книги и проекты, так что готовься увязнуть в самообразовании.

А почему именно b-tree, а не скажем LSM?

Спасибо большое! На полноценный sql сервер не замахиваюсь, скорее свой вариант кассандры но без SSTable

Все предельно просто - в постгре по умолчанию btree - начал гуглить детали, понравилось, вот реализовал на коленке. Возможно когда нибудь добавлю другие варианты, благо это ж петпроджект

Делал своё B+-Tree пару последних лет, на нём работает сейчас вот этот чатик: http://fintank.ru:8080/ (доступ на запись по запросу)

Можно в телеге вопросы клепания своих B+-Tree обсудить в этом чатике в телеге: https://t.me/makedbms

B+-Tree крайне примитивная структура, когда дело доходит до диска. Оно ведь B. Просто множество блоков. Пиши их в файл как вздумается.

1. Просто открываешь файл и складываешь последовательно все блоки. Это снепшот.

2. Если решил записать в файл блоки не как они есть в памяти, а только ненулевое содержимое и поэтому они вышли разных размеров, то в начало файла придётся положить табличку смещений.

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

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

5. Если блок надо модифицировать, его надо сначала записать в бинлог или в double write buffer (как сделано в innodb), а потом уже в целевое место, чтобы при падении питалова не получить в основном месте полблока старых, полблока новых.

Это всё в целом несложно и осмысляемо школотой, а любые велосипеды в этой области не страшны и просты.

Сорян: https://t.me/makebtree

А почему именно b-tree, а не скажем LSM?

Сравнение холодного с красным. LSM - это про более высокоуровневую структуру. LSM можно сделать из b-tree, их хештаблиц или других херней.

попробуй реализовать свой MUMPS сервер

как ее хранить и модифицировать на диске

mmap-ить страницами (page table).

про btree прочитай про MUMPSы, например книжку Евгения Коротаева (автора MiniM) у него на сайте (в разделе документация последняя ссылка на PDF).

MUMPS СУБД = «кеширующий сервер глобалов и рутин»

то есть, есть сервер СУБД многопользовательский многопроцессный (команда JOB порождает новые процессы). есть «рутины» = процедурный ЯП навроде фокала. есть переменные – локальные переменные процесса или «глобалы» = персистентные переменные уровня СУБД, всех процессов. есть транзакции, локи, ACID, индексы, процедуры в рутинах, сопрограммы и т.п.

в качестве примеров реализации MUMPS можешь посмотреть GT.M, Yottadb, okane’s MUMPS на C++ с книжкой, Ray Newman MUMPS – всё гуглиться на саусфоржде, гитабе и официальных сайтах, с исходниками и в случае O’Kane вместе с книжкой.

чем интересен MUMPS (если не ржать как конь над анекдотичной «The daily WTF: The case of MUMPS»).

во-первых, есть public domain стандарт и реализации. во-вторых, это язык на котором можно ЦЕЛИКОМ написать приложение БД (с запросами, индексами, CHUI текстовым интерфейсом, вебсервисами и т.п.). в-третьих, язык относительно простой. в-четвёртых, структуры данных ОЧЕНЬ мощные.

глобал это многомерный разреженный глобальный массив – по сути хеш-таблица у которого есть ключ и значение.

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

то есть, не всё таки first class object.

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

в итоге, структура данных «глобал» – это хеш-таблица с ключом-строкой (получается из индексов массива – составными ключи, приведённые к строке) и значением-строкой (тоже все остальные значения приводятся к строкам).

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

в целом, низкоуровневость МУМПСа как языка, безсхемность структуры глобал – позволяет очень гибко хранить и изменять структурированные иерархические значения, кешировать в памяти.

поэтому например эффективность МУМПСа как СУБД скорее всего определяется тем, насколько эффективно удалось эти элементы закешировать.

в отличие например от СУБД Pumpkin на Rust-е, здесь ключи эффективно сжимаются, кешируются, используя совместно общие элементы.

то есть, если структура такого глобала продумана правильно – в нём можно эффективно хранить иерархические составные данные (деревья, списки, структуры, …, объекты).

… там в общем, много всего можно порасказать за МУМПСы.

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

по сути, МУМПС как язык похож на такой «ассемблер базы данных». у которого есть сопрограммы, параллельные процессы, многозадачность, эффективная универсальная структура данных (глобал).

хотите запросы или индексы – делайте процедурами вручную.

с одной стороны, странно после SQL. с другой, мы имеем предсказуемую контролируемую производительность вместо непонятно чего там декларативного sql profiler наоптимизирует.

и в целом, более стандартизированное и предсказуемое ВСЁ.

в общем, на тему «чем лучше SQL» – читай у Е. Каратаева в блоге про «почему мне не нравится SQL», критика вполне себе справедливая.

… на тему проектов, которые было бы интересно реализовать.

вот если посмотреть по ссылкам, что я тебе выше привёл.

• Ray Newman’s MUMPS V1 – простой интерпретатор

• O’Kane’s MUMPS – MUMPS как библиотека на C++, компиляция в С++ (нетривиально из-за косвенности и т.п.)

• GT.M, Yottadb – достаточно эффективный компилятор языка M в *.o объектники напрямую, поддержка ACID, транзакций, Unicode из коробки

• MiniM – в целом, простая и эффективная реализация (MiniMono – встраиваемая реализация) но без исходников

было бы интересно запилить собственную реализацию на более других чем С/С++ языках (в отличие от GT.M, Yotta) – на аде, pony, go либо Rust.

например, попытаться более эффективно реализовать многозадачность/многопоточность. упростить кроссплатформенность «из коробки». упростить интеграцию с POSIX и прочее.

ещё можно на развития MUMPS-а как языка посмотреть – Cache Object Script, EsiObjects*, PSL, MAGIC, MSH* (в * = даже исходники какие-то имеются опенсорсные).

в идеале, язык можно развить в сторону какого-нибудь LUA.

а само хранилище глобалов использовать как библиотеку.

без языка именно M.

в этом направлении движутся GlobalsDB (=Cache-MUMPS), Yottadb (новый современный форк GT.M), MiniMono.

Re2: попробуй реализовать свой MUMPS сервер.

на тему эффективности хранения

по прочтении книжки «Linkers and Loaders» by Jonh R. Levine про это самое (особенно, примеров – исходников линкера на перле)

возникает такая идея, что всё то же самое на МУМПСе можно было бы реализовать не сложнее, да эффективнее.

вообще, на МУМПСе можно реализовать и ассемблер. который может работать напрямую с базой данных, с символьными таблицами, неогранниченного размера. напрямую в отсортированных сбалансированных BTree+ деревьях.

в итоге, приходит в голову идея эдакой МУМПС ОС.

в которой например, МУМПС СУБД реализована в ядре. нативная естественная многопроцессность/многопоточность.

страница в памяти = страница на диске = кусок кешируемого Btree блоба.

а в блобах можно хранить и произвольные данные – но уже индексированные.

файловую систему же здесь реализовать можно и виртуально, наподобие FUSE.

ну то есть: в такой МУМПС ОС по умолчанию файлов, ссылок и директорий нет, это виртуальные искусственные сущности. которые через FUSE (или наподобие plumber в Plan9 FS) отображаются в реальные – глобалы,локалы, процессы,рутины, индексы.

и например редактируя какой-нибудь /etc/configuration.conf мы на самом деле правим глобал МУМПСа.

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

и на уровне языка М и рутин (либо какой-то простой ОО надстройки над ним типа MSH, Lua) – происходит интеграция приложений.

в этом смысле, СУБД МУМПСа выполняет по сути примерно те же самые действия, что и ядро ОС:

• отображает страницы на диске в страницы в памяти в выскокоуровневые структуры (mmap файлы, страницы подкачки, глобалы МУМПСа, блобы в глобалах чанками (см. книжку))

• выполняет многозадачные многопользовательские процессы

• выполняет серверные рутины, которыми поддерживаются нужные абстракции вроде ООП и индексов

• поддерживает транзакционность, ACID, многопользовательность – вот это всё.

то есть, mmap нужных страниц – очень эффективное хранение (осталось догадаться чего).

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

ещё можно посмотреть исходники Quake, Doom (начёт Binary Space partition Tree, хотя там PAK отдельный псевдофс) или btrfs (и почитать Эдика, правда, Шишкина – который ReiserFS4 про BTree+ вообще ругался, дескать устарело, внутренняя фрагментация и примитивно всё).

я так подозреваю, основная составляющая эффективности МУМПСов состоит в том, насколько эффективно реализовано кеширование и упаковка ключей-индексов (совместно используя общие части, в отличие от какого-нибудь Pumpkin на расте).

пункт 3 может разрастись в полноценное журналирование (демон журнала в GT.M/Yotta).

FreeM – это вроде как актуальный поддерживаемый форк Ray Newman’s MUMPS V1.

MSH – предлагаемое развитие языка M в сторону ООП гитхаб

Kevin O’Kane homepage – особенно рекомендую другую книжку, ISR с примерами

– там у него кстати, тоже BTree в постргессе хранятся.

ну то есть, такой «неправильный МУМПС», который конпелируется в С++, подключается как библиотека, а физически транзакционность реализуется через постгрю.

правильный, по идее – реализовать эффективную подкачку страниц, диска, памяти этого самого «кеширующего сервера глобалов и рутин»

остальное всё вроде бы легко гуглится

ещё можно EsiObjects посмотреть на сорсфорже, особенно сайт с примерами и обучалками.

как пример того, как ООСУБД может быть реализовано поверх глобалов МУМПСа.

то есть, EsiObject опенсорсный реализует примерно то же самое, что Cache Object Script проприетарный либо расширения языка типа MSH и прочие.

я так думаю, нужно что-то LUA-метатаблиц-подобное слепить, с православными first class objects уровня ООСУБД.

ещё можно EsiObjects посмотреть на сорсфорже, особенно сайт с примерами и обучалками.

https://sourceforge.net/projects/esiobjects/
Этот?

Это же заброшенный проект

MicroMumps – вот ещё реализация MUMPS-а под CP/M под Z80.

ЕМПНИП, целиком на ассемблере.

нечто подобное в «MUMPS OS» по идее не очень сложно развить.

либо раздобыть исходники последнего CP/M MP/M многозадачного на PL/M. и переписать его на PL/M, ога =)

а потом под PL/I и PL/I-KT компилятор :))

эдакий TempleOS теплый ламповый мейнфреймовый, только без божественного Holy C+, а с М либо сразу MSH =)

это не важно что заброшен.

он всё ещё интересен, содержательно как реализация ООСУБД на МУМПСЕ, на чистом M.

ещё там есть парсер языка M на ANTLR V2

няшная сишечка для микроконтроллеров: uM/main.c

вот например из FreeM dbformat

Cassandra - это не про оптимизацию хранения дерева на диске <_<

сравнение быстродействия БД заметка со ссылками, например статья

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

и нужны ли там вообще транзакции, какие и где именно.

и вообще у него цикл статей

ещё интересное сравнение: fastinsert.m

• оригинальная статья fast-sqlite-inserts :

hw: MacBook Pro, 2019 (2.4 GHz Quad Core i5, 8GB, 256GB SSD, Big Sur 11.1)

Variant Time Rust 33 seconds PyPy 150 seconds CPython 510 seconds

Current Best: 100M rows inserts in 33 seconds

• fastinsert.m: см. исходники и примеры.

For example on a Raspberry Pi Zero W running Debian Bullseye
;   $ yottadb -run fastinsert 1E6
;   Set 1,000,000 nodes in 1.112911 seconds using 4 processes at 898,544 nodes/sec
;   $
;   $ yottadb -run fastinsert 1E7
;   Set 10,000,000 nodes in 12.804218 seconds using 4 processes at 780,993 nodes/sec
;   $
; and on a home-built AMD Ryzen 7 3700X 8-core machine running Ubuntu 21.04:
;   $ yottadb -run fastinsert 1E7
;   Set 10,000,000 nodes in 0.256053 seconds using 16 processes at 39,054,415 nodes/sec
;   $ yottadb -run fastinsert 1E8
;   Set 100,000,000 nodes in 2.602755 seconds using 16 processes at 38,420,827 nodes/sec
;   $
; Note that using the MM access method with journaling disabled, the database is fully
; persistent on normal process completion, but is not recoverable if the system crashes
; during test. Turning on journaling makes it recoverable, e.g. on the Ryzen PC using
; the command: mupip set -journal=enable,nobefore -region DEFAULT
;   $ yottadb -run fastinsert 1E7
;   Set 10,000,000 nodes in 0.331300 seconds using 16 processes at 30,184,123 nodes/sec
;   $ yottadb -run fastinsert 1E8
;   Set 100,000,000 nodes in 3.362727 seconds using 16 processes at 29,737,769 nodes/sec
;   $

то есть, без журналирования

set 100,000,000 nodes in 2.602755 seconds using 16 processes at 38,420,827 nodes/sec

с журналированием и транзакциями

Set 100,000,000 nodes in 3.362727 seconds using 16 processes at 29,737,769 nodes/sec

сравни с исходным SQLite 100M за 33 секунды

– в 10 раз быстрее.

это полный WIN, я щитаю. // хотя да, тесты всё ещё голимая синтетика_

Анонима понесло. Ты что, всю жизнь потратил на изучение b+tree и оно нигде не пригодилось?

Почему, пригодилось.

про BTree+ вообще ругался, дескать устарело

И что он предлагает на замену?

у него там в Reiser4fs свои особые уличные деревья

mmap-ить страницами (page table).

Так практически никогда не надо делать. Абсолютно неконтролируемое поведение ядра и лаги в рандомных местах по 300 миллисек