создание параллельного дерева b + (c)

Question

Я сейчас пытаюсь сделать дерево b + параллельным.

До сих пор подход, который я имел в виду в качестве отправной точки, заключался в повторении дерева при вставке, блокировке каждого узла (каждый узел имеет свою собственную блокировку) и разблокировке после получения блокировки следующего узла в дереве, пока узел, у которого есть дочерний элемент, имеющий порядок ключей b + tree - 1, поскольку все, что находится под этим узлом, может быть изменено, после чего все необходимые операции вставки выполняются и узел разблокируется.

Это, очевидно, очень наивный подход и не дает много возможностей для параллелизма, поэтому мне было интересно, есть ли лучший способ сделать это? Будем весьма благодарны за любые материалы!

Answer 1

Я только что закончил один проект по реализации параллельного дерева B +. Вы можете найти некоторую интуицию из CMU 15-445 (Системы баз данных):

https://15445.courses.cs.cmu.edu/fall2018/slides/09-indexconcurrency.pdf (слайды) https://www.youtube.com/watch?v=6AiAR_giC6A&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=9 (видео)

Один из способов сделать это называется "защелка защелки". По сути, вам нужен RWLock для каждого узла.

Когда вы ищете конечный узел, вы добавляете блокировку чтения (поиска) или записи (вставки / удаления) на каждый посещаемый вами узел. Как только вы обнаружили, что узел «безопасен» (т. Е. Он не будет разделяться для вставки или не будет сливаться / перераспределяться с соседями при удалении), вы можете снять блокировки своих предков, поскольку вы знаете, что изменение ограничено этот узел. Таким образом, вы приобретаете замки спереди и отпускаете замки сзади, ходя как краб, поэтому это называется «защелка защелки» (здесь я неправильно использую «защелка» и «защелка»)

Это может быть сложно реализовать, хорошая блокировка :)