The Buffer Tree (Lars Arge).

Почему оценка сложности (в единицах IO)

IO

закрадывается смутное догадко ... могут лежать во внешней памяти

хороший догадко

B-деревья только тем и прекрасны, что снижают число операций за счет малой глубины. В RAM дешевле двоичными деревьями балансировать

Нафига там такой принципиальный момент постоянно оговаривается, что количество фанаутов у внутренних нод очень дофига, сильно больше «обычного Б-дерева»?

Всю статью не читал, но вроде у них получаются некие вариации b+ дерева. Жирные узлы ему нужны чтобы а) за одну IO операцию больше данных читать/писать, б) при изменении контента дерева меньше трогать блоков, в) меньше съедать памяти на технические данные (в большом блоке выше доля полезной информации по отношению к размеру блока).

Чё это вообще за B?

Это размер IO блока в элементах. Понимаешь ли, нельзя прочитать с HDD произвольное кол-во байт, можно только определённое кол-во блоков (секторов) и тоже самое с записью. Потому все операции ввода вывода на такие носители стараются делать блоками размером кратным сектору и вних же (random IO + seq IO) измерают время (сложность) операций.

У меня закрадывается смутное догадко, что буферы M поделены на блоки B и могут лежать во внешней памяти.

Все данные дерева должны размещаться в энергонезависимой памяти и некоторые из них могут подгружаться в RAM, потому все буфера в RAM и «диск» состоят из одинаковых блоков для простоты их считывания, записи и адресации из других блоков. В частности все данные M/B блоков есть и в оперативной, и во внешней памяти.

B-деревья только тем и прекрасны, что снижают число операций за счет малой глубины. В RAM дешевле двоичными деревьями балансировать

Вопрос не про B-деревья, а про блоки размера M из статьи. Нечетал, но осуждаешь, видимо...

В RAM не дешевле двоичными деревьями, в RAM дешевле B-tree тоже, потому что память иерархична и у проца есть кеш. Обращаясь в RAM к указателю размером 8 байт ты загружаешь из неё 64 байта, всё как с диском.

Жирные узлы ему нужны чтобы а) за одну IO операцию больше данных читать/писать

Ну взял бы обычное Б-дерево, увеличил бы размер блока тупо в настройках и радовался.

Вопрос зачем именно в этой структуре с буферами нужны сильно большие фанауты.

Это размер IO блока в элементах.

Вопрос не в этом. Вопрос в том, что «а при чём тут вообще B? Мы же флашим тоже в буфера дочерних нод, нахрен нам вообще какой-то IO?»

Все данные дерева должны размещаться в энергонезависимой памяти и некоторые из них могут подгружаться в RAM, потому все буфера в RAM и «диск» состоят из одинаковых блоков для простоты их считывания

Ну вот вопрос не про Б-дерево вообще, а про эти вот буферы размера M.

https://www.lektorium.tv/lecture/13930

Слушал, не нашёл там ответов на свои конкретные вопросы.