Очередной какой-то там пашэпроект.

http://fintank.ru:9090/

Что это.

По ссылке - тестовая морда в самописный B+-Tree (с дикимичи фичами).

Зачем писать своё B+-Tree
Незнаю, чё-то все их пишут в мире, наверное это круто. Да ещё вещь не простая, каждый раз что-то своё получается под свои задачи.

Как понять.

Зайдя по ссылке видим корень дерева.
Сверху написано level 5. Значит дерево высотой 6 (самый нижний листовой уровень - level = 0).
Почему такое высокое - оно тестовое с размером страницы 512 байт, чтобы блоки почаще делились и проявлялись всякие краевые эффекты.
В это дерево напихано 1М элементов. Элемент - это key=value, но их только половина от ляма. Остальная половина элементов - это другие упоротые вещи, о них речь далее.
В корне мы видим, что у нас там лежат два разделяющих (всё наше пространство) ключа.
По текущей ссылке это: пустая строка и cgLQ.
Почему там два - ну так сложилось, обычно больше.
Каждый ключ ссылается на блок уровнем ниже (level 4).
Если вы хотите найти что-то, что в порядке сортировки строк идёт после cgLQ - жмите на эту ссылку, если до - жмите на предыдущую.

Вот скажем я жму на предыдущую (которая "пустая строка). Прихожу в этот блок: http://fintank.ru:9090/?block_id=451
Там навалены разделяющие ключи, которые все до cgLQ.
Ну и так далее.
Жмём на Bz: http://fintank.ru:9090/?block_id=104958
Жмём на CwvNtFkJk: http://fintank.ru:9090/?block_id=59010
Жмём на CzpDbTlmooFIljFDWNKzGy: http://fintank.ru:9090/?block_id=66489
Жмём на Czz: http://fintank.ru:9090/?block_id=131180

Оппа, пришли на level 0.
Это листовой блок, он хранит сами полезные данные, а не информацию роутинга.

В данном листовом блоке мы видим несколько ключей:
Czz
CzzKYs
CzzZhYTyER <-- обсудите тот факт, что только у этого ключа тип key=value (KV).
D

Остальные ключи оказались не просто key=value, а массивами (листами).
Например ключ Czz - хранит массив из 2 элементов:
@@ocYDrqX
@@UOV

Это пример "дикой фичи" данного B+-Tree: key=[array]. Есть там ещё key=[set] и ещё key=[map], например.
Зачем? - спросит очередной формоклёп с горы.
"Разве нельзя было просто сериализовать как-нибудь что угодно, включая список, в строку и сохранить в любое key=value" - спросит он?
Можно. Но так любая псина умеет.
А чё ты будешь делать, если тебе надо вставить в конец списка? Достанешь ключ, десериализуешь, засериализуешь и пересетишь?
Ясно. Сам так живи, мы не хотим.
Нам надо так: список длинной 6 млрд элементов и мы вставляем в его середину, да так, чтобы это было за время вставки маленького key=value и чтобы индексы всех 3-млрд-после-середины элементов автоматом сдвинулись на 1 (или N, сколько мы там вставляем).
Т.е. список может занимать много блоков данного B+-Tree.
И мы не хотим трогать все эти блоки.
Я не знаю сколько блоков займёт 6 млрд строчек.
И я хочу потрогать максимум 2-3 блока, чтобы выполнить вышеозвученное требование.
И хочу вообще на диск не ходить, если уже потрогал эти блоки и снова надо в середину вставить.
Короче нужен не какой-то детский уровень, а чтобы сам товарищ Сталин руку пожал.

Посмотрим на ключ D в данном листовом блоке.
В нём лежит 15 элементов.
Но это только кусок, точнее начало. Мы не зря в этот блок пришли.
В нём кончается C-пространство и начинается D-пространство, скажем, например.
Сколько элементов лежит в списке D я не знаю.
Дохрена.
Мы видим голову.
Выйдем на уровень выше.
Кнопки выше нет, юзайте назад в браузере или смотрите выше наш путь в этот листовой блок.
А на уровне выше мы видим разделитель D:15.
Он показывает на блок, в котором список D продолжается с элемента 15.
Можно туда сходить, там всего 3 элемента и в блоке свободно 90% памяти.
"Чё так не плотно" - спросит читатель.
Ну уплотнялка тут решила не работать или выключена, не помню.
Всё потому, что когда в список D в этом B+-Tree инсертились ключи, то они втыкались в рандомные смещения: ну типо 4, 1, 3, 2, 4, 1, 0, 3, 2....
Инсерт в позицию 0 предполагает что старый 0 становится 1.
Чё-то я щас смотрю на этот D, у него только голова плотная, остальное надроблено по 1 элементу-на-блок.
Короче ладно, это потом пофиксим.
Можно посмотреть на этот блок: http://fintank.ru:9090/?block_id=59010
Видно что тут индексы у D шагают на сотни.
Если я хочу элемент списка >= 709,то ясно по какому маршруту идти.
Вся структура, ясно дело, относительная, на новом уровне надо всё суммировать к 709.
Относительная она потому, что... долго объяснять... короче чтобы разные куски маршрутов были максимально независимы.
Так мы добиваемся того, что при сдвиге всех элементов в 6-млрд-элементном списке можно пошевелить только какой-то верхний уровень, не думая больше ни о чём. В общем, подумайте и поймёте. Очевидное решение довольно.
А вот тут: http://fintank.ru:9090/?block_id=104958 есть D:963. В общем, можно сказать что в D лежит больше 963 элемента точно.
Больше чем D:963 + D:590 ну и т.п. - сходите по той ветке, суммируя максимальные индексы разделителей, узнаете.
Там оказывается ещё список DA валяется.
А тут лежит последний ключ дерева: http://fintank.ru:9090/?block_id=114364
Он называется zzzo и он оказался тоже списком из 1 элемента.
Нахрен нужны списки обычному человеку и подобный простой доступ к его рандомным кускам и диапазонам?
Например, чатики любых размеров хранить. Большой чатик из 10 млрд сообщений просто жрёт блоки, а доступ к любой месаге по порядковому номеру моментален. Чатик из 1 сообщения занимает как 1 жалкое key=value - удобно, дёшево, молодёжно.
Можно дать юзеру создать сто миллиардов топиков в день и никто не умрёт.
А в структурах типа key=[set] можно хранить инфу из кнопки лайков. Пихаешь туда id юзеров, оно гарантирует их уникальность и может быстро сказать количество элементов в сете - можно нарисовать циферку лайков.
Массивы, сеты (множества), мапы (словари) и прочая дичь, рубить которую на куски умеет B+-Tree - это очень мощно, потому что блоки - вещь децентрализуемая, компактная, сжимаемая и очень сильно крупнологарифмическая, что в целом приводит к существенной бесплатности происходящего.
Бенчмарки: в среднем инсерт сюда стоил 7 микросек, селект стоил в среднем 0.7 микросек.
Блоки нарублены плохо, во многих 90% пустого пространства.
Стоит включить мёржилку, чтобы при инсертах она смотрела на соседей и объединяла их.
Это сожрёт сколько-то тактов, но селекты будут ещё быстрее, блоков-то будет меньше раз в 10.
Если делать размер блока не наркоманский, а нормальный, где-нибудь в 65 Кб, то уровней будет не 5, а естественно штуки 2-3.
Чтокакбе намекает нам на то, что это надо протестить.
Вообще у всяких Дональдов-Кнутов описаны B*-Tree (звёздочка) и там есть какие-то соотношения про 2/3 и мёржинг, но в реальности нужно думать.
Могу бухнуть с экспертами в этой области.
А, да, я ещё статистику считаю конечно же: скажем, если с вероятностью 0.9 втыкали в конец блока (кто-то льёт в конец списка или инсертит возрастающие ключи), то при делении блока левый сын получит 90% старых ключей, а всё свободное место и 10% старых ключей достанется перспективному правому сыну. Левые обычно социалисты. Хорошо примерчик получился про "перспективый", конечно. Мемно!
Ну и вот. Я незнаю чё в этот раз так наделилось странно. А вспомнил, мёржилка не работала вообще и был полный рандом во вставке.
Да, конечно тестировали на совпадение данных в этом B+-Tree с референсным хранилищем - всё совпадает, обижаешь.
Нормальные люди ещё умеют сжимать ключи, скажем сохранять только общие префиксы.
Миллиард литературы есть по теме, конечно.
Досвидания.