B-деревья и их разновидности во внешней памяти

На данном семинаре разбирались B-деревья и их разновидности. Основная их отличительная черта — большая степень ветвления, позволяющая радикально понизить высоту дерева, а значит уменьшить количество случайных обращений к диску. И все же B-деревья не способны эффективно решать задачи, в которых количество операций со структурой данных велико. Например, невозможно эффективно отсортировать данные во внешней памяти с помощью B-дерева. На помощь приходит batching: нужно запоминать вставки, обрабатывая их не поотдельности, а группами. На этой идее и построено буферирозованное дерево, изучение которого было начато на этом занятии. Источник: https://cotass.wordpress.com/2012/03/11/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-%D1%81%D0%BF%D0%B5%D1%86%D0%BA%D1%83%D1%80%D1%81-%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0-%D0%B1%D0%B0%D0%B1%D0%B5%D0%BD%D0%BA%D0%BE-%D0%B8-%D0%B4%D0%BE%D0%BA%D0%BB-10/ Плейлист: https://www.youtube.com/playlist?list=PLuWypj7F_mQlIBhQwfb8qgRjI-qZuJx1U