История изменений
Исправление aist1, (текущая версия) :
Быстрый вопрос. Ты, наверное, решил, что под BTREE я имею в виду бинарные деревья? Я имею в виде именно b-tree, как семейство производных структур.
Если говорить про бинарные деревья и LSM, то асимптотика произвольного доступа у них одинаковая — O(log2(N)). Т.е. если какое-то бинарное дерево и «сливает» LSM, то это просто по причине того, что бинарное дерево адаптировано под модель памяти RAM(*), а не блочных устройств (DAM).
Асимптотика B-tree на много лучше, чем у бинарных деревьев — O(LogB(N)), где B >> 2. Они в этом плане заруливают и бинарные деревья в RAM, и LSM в DAM, так как требуют меньшего количества чтения блоков.
(*) В современной RAM с прозрачной иерархией кэшей, чтобы ты не «включал зануду».
Исправление aist1, :
Быстрый вопрос. Ты, наверное, решил, что под BTREE я имею в виду бинарные деревья? Я имею в виде именно b-tree, как семейство производных структур.
Если говорить про бинарные деревья и LSM, то асимптотика произвольного доступа у них одинаковая — O(log2(N)). Т.е. если какое-то бинарное дерево и «сливает» LSM, то это просто по причине того, что бинарное дерево адаптировано под модель памяти RAM, а не блочных устройств (DAM).
Асимптотика B-tree на много лучше, чем у бинарных деревьев — O(LogB(N)), где B >> 2. Они в этом плане заруливают и бинарные деревья в RAM, и LSM в DAM, так как требуют меньшего количества чтения блоков.
Исходная версия aist1, :
Быстрый вопрос. Ты, наверное, решил, что под BTREE я имею в виду бинарные деревья? Я имею в виде именно b-tree, как семейство производных структур.
Если говорить про бинарные деревья и LSM, то асимптотика произвольного доступа у них одинаковая — O(log2(N)). Т.е. если какое-то бинарное дерево и «сливает» LSM, то это просто по причине того, что бинарное дерево не адаптировано под модель памяти RAM, а не блочных устройств (DAM).
Асимптотика B-tree на много лучше, чем у бинарных деревьев — O(LogB(N)), где B >> 2. Они в этом плане заруливают и бинарные деревья в RAM, и LSM в DAM, так как требуют меньшего количества чтения блоков.