Сравнить реализацию дерева B+: хранение внутренних узлов на диске

Question

Есть ли реализация, где внутренние узлы дерева B+ также хранятся на диске? Мне просто интересно, знает ли кто-нибудь о такой реализации или видит реальное преимущество, делающее это таким образом? Обычно каждый сохраняет листовые узлы на диске и разрабатывает дерево B+ согласно потребности.

Но также возможно сохранить текущее состояние внутренних узлов дерева B+ (заменив указатели на номер блока диска, на который он указывает): я вижу, что существуют другие проблемы, такие как синхронизация внутренних узлов в памяти с блоками диска: но дерево B+ может быть реализовано на nvram или, скажем, на батарейке с драмом или каким-либо другим способом, чтобы поддерживать его в синхронизации.

Просто интересно, кто-нибудь уже реализовал это так, как bcache в Linux или другую реализацию?

ура, cforfun!

Answer 1

Все постоянные реализации B+Tree, которые я когда-либо видел - в отличие от чисто "временных" структур в памяти - хранят оба типа узлов на диске.

Для этого не нужно будет сканировать все данные (внешние узлы, так называемый "набор последовательностей") при каждой загрузке, чтобы перестроить индекс, что выполнимо, только когда вы работаете с небольшими объемами данных или очень обстоятельства.

Я видел однопользовательские реализации, которые синхронизируют образ диска только тогда, когда менеджер страниц извлекает грязную страницу и закрывает программу, что приводит к тому, что часто используемые внутренние узлы, которые редко заменяются / извлекаются, могут работать без синхронизации. на диск в течение длительного времени. Это в некоторой степени оправдано тем фактом, что внутренние ("индексные") узлы могут быть восстановлены после сбоя, так что только внешние ("данные") узлы нуждаются в полной отказоустойчивой обработке персистентности. Преимущество таких схем состоит в том, что они устраняют потерянные записи для узлов, близких к корню, частота обновления которых достаточно высока. Вспомните SSD, например.

Одним из способов повышения эффективности работы дисков для постоянных структур в памяти является сохранение только журнала на диск и перестроение всего дерева из журнала при каждом перезапуске. Один очень успешный пакет Java использует этот подход с большим преимуществом.