При слиянии уровней LSM очень легко построить что-то вроде Btree для сливаемого уровня.
Мы генерируем K=log1000N последовательностей, в последовательности уровня i=1..K-1 пишем ключ и ссылку на адрес (страница + смещение) в последовательность i-1. В нулевую последовательность пишем пары ключ+данные
(
Read more... )