Scapegoat-деревья

[kostja]

Эти деревья использовались в Tarantool 1.5 и 1.4 как наиболее компактные отсортированные структуры данных. К сожалению, из-за того что худший случай при вставке очень плох, они не подходят для предсказуемой производительности на больших объёмах — пересортировка при дереве в пару миллиардов записей может занимать секунды. Поэтому в 1.6 мы отказались от scapegoat деревьев в пользу B-tree в памяти с компрессией указателей на вершины.

[voidnugget]

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

Мне в этом плане больше импонируют ART-деревья — с ними достаточно просто реализовать вертикальное масштабирование key-value хранилищ.

[leshabirukov]

Понимая, что в худшем случае нам, возможно, придётся посчитать вес половины дерева — мы видим ту самую сложность O(N) в худшем случае… амортизированная сложность операции не превысит O(log N)

После любой вставки, а не только в худшем случае, нам надо перепроверить баланс корня, а значит обойти всё дерево -> O(N). Или я чего-то не понимаю?

[Mrrl]

Они проверяют не полную α-сбалансированность дерева, а всего лишь условие height <= log_1/α(N)+1, где height — глубина, на которой оказался новый узел. Вот если оно нарушается, то начинают считать веса поддеревьев.

[leshabirukov]

Спасибо, теперь понятно. Автору стоило бы об этом написать, а вот объяснения сократить раза в два. А само дерево интересное, дёшево и сердито.

[klirichek]

Какая тонкая статья к году деревянного козла!