Двоичные деревья не особенно подходят для многопоточности, потому что перебалансировка может вырождаться в модификации всего дерева. Кроме того, глобальный мьютекс очень негативно повлияет на производительность.
Я бы настоятельно рекомендовал использовать уже написанные потокобезопасные контейнеры. Например, Intel TBB содержит concurrent_hash_map.
Однако, если вы хотите выучить , вот несколько советов по созданию параллельного отсортированного ассоциативного контейнера (я полагаю, что полное введение будет не только вне моей досягаемости, но и неуместно, здесь).
Устройство чтения / записи
Вместо обычного Mutex вы можете использовать Mutex для чтения / записи. Это означает распараллеливание операций чтения, в то время как операции записи остаются строго последовательными.
Собственное дерево
Вы также можете создать свое собственное красно-черное дерево или дерево AVL. Расширяя древовидную структуру мьютексом Reader / Writer для каждого узла. Это позволяет блокировать часть дерева, а не всю структуру, даже при перебалансировке. например, вставки с достаточно далеко расположенными клавишами могут быть параллельными.
Пропуск списков
Связанные списки гораздо более поддаются одновременным манипуляциям, поскольку вы можете легко изолировать модифицированную зону.
A Список пропусков основывается на этой силе, но дополняет структуру, чтобы обеспечить доступ O (log N) по ключу.
Типичный способ обхода списка - использование идиомы hand hand *1041*, то есть захват мьютекса следующего узла перед освобождением одного из текущего узла. Пропускные списки добавляют второе измерение, поскольку вы можете погружаться между двумя узлами, освобождая их оба (и позволяя другим ходячим идти впереди вас).
Реализации намного проще, чем для деревьев двоичного поиска.
Стойкие
Другой интересной частью является идея постоянных (или полупостоянных) структур данных, часто встречающихся в функциональном программировании. Дерево бинарного поиска особенно подходит для этого.
Основная идея - никогда не менять узел (или его содержимое), когда он существует. Вы делаете это, разделяя изменчивую head , которая будет указывать на более позднюю версию.
- Чтение: вы копируете текущий заголовок, затем используете его без беспокойства (информация неизменна)
- Для записи: каждый узел, который вы бы изменили в обычном дереве, вместо этого копируется, а копия модифицируется, поэтому вы каждый раз перестраиваете часть дерева (вплоть до корня) и обновляете head указать на новый корень. Существуют эффективные способы восстановления баланса при спуске дерева. Пишет последовательно
Основным преимуществом является то, что версия карты всегда доступна. То есть вы всегда можете прочитать , даже если другой поток выполняет вставку или удаление. Кроме того, поскольку для доступа read требуется только одно одновременное чтение (при копировании корневого указателя), они практически не блокируются и, следовательно, имеют отличную производительность.
Подсчет ссылок (встроенный) - ваш друг для этих узлов.
Примечание: копии дерева очень дешевы:)
Я не знаю ни одной реализации в C ++ ни параллельного списка пропусков, ни параллельного полупостоянного дерева двоичного поиска.