Как мировые лидеры-имплементаторы B+-Tree (авторы всяких там движков InnoDB или Postgres) успешнее всего решали задачи «дай число ключей в дереве между A и B»?
Могу сходу напридумывать способов облегчать такие запросы, простейший: в каждом PIVOT хранить число ключей во всём поддереве, на которое он показывает. Тогда находим просто 2 итератора на lower_bound(A) и upper_bound(B) и суммируем все такие чиселки на всех PIVOT между ними. Учитывая, что не обязательно ходить по PIVOT-ам в блоках уровня 1 (0 означает LEAF-блок), а можно часто пройтись и по блокам выше, суммируя числа крупнее (критерий: блок верхнего уровня покрывает весь диапазон блоков уровня ниже, по которым мы собирались пойти), то всё можно сделать быстро. Физически это будет выглядеть примерно так: сходили вглубь до LEAF для A, сходили вглубь до LEAF до B, потом поднялись-собрали, собрали по крыше, опустились-собрали. Трапеция такая. Ну вы поняли. Но недостаток тут в том, что тебе надо на каждый инсерт ключа инкрементить чиселки на всем пути выше, по которому ты пришёл в LEAF и в целом больше блоков в дереве будет грязными из-за этого, хотя наверное пофиг.
Это к «задаче про лайки». Допустим я решил хранить число лайков в комменту в какой-то наивной реализации B+-Tree. Коммент - это uint64 (id сущности, которую лайкнули - docid), лайк - тоже uint64 (кто лайкнул - userid). Инсертим в дерево ключ K = uint128 (конкатенация двух ID выше - (docid << 64 + userid)). Такой ключ может быть только один. Всё хорошо. Медленно - это достать число лайков к нашему docid. Для этого надо достать число ключей в подинтервале [ID:0, ID+1:0), что при паре лямов лайков к какому-то посту не-больно только при каком-то ненаивном подходе к этому, типа описанного выше.
Вопрос: чё там в постгресах-мускулях понаверчено физически в реальности для оптимизации такого?
Как хранить лайки иначе спрашивать не буду, и так знаю - во всяких фейсбуках просто пишут свою микро-субд, представляющую собой логически std::map< uint64_t, std::set<uint64_t> > и кайфуют. Вопрос был именно про кейс, когда Вася решил докопаться именно до B+-Tree для такой задачи. Мало ли где ещё и для чего кто-то хочется число ключей в подинтервале.
