alizar
Один из сотрудников Google в 20% свободного времени разработал и выложил под свободной лицензией библиотеку cpp-btree (С++ B-Tree), которая содержит контейнеры, работающие как map, set, multimap и multiset из стандартной библиотеки шаблонов (STL).
Разница в том, что контейнеры в STL реализованы на красно-чёрных деревьях, а аналогичные контейнеры cpp-btree - на B-деревьях. При этом в определённых ситуациях достигается существенный выигрыш в использовании памяти (на элементах маленького размера) и в производительности (на больших размерах контейнера).
B-деревья известны как инструмент для работы с дисковой памятью: базами данных и файловой системой. Но те же свойства, которые дают выигрыш там, позволяют эффективнее использовать и оперативную память. Каждый узел красно-чёрного дерева содержит один элемент, требует три указателя плюс по биту информации на элемент для сбалансированности. Для сравнения, контейнеры на B-деревьях хранят несколько элементов на узел, поэтому уменьшают оверхед указателей и экономят значительное количество памяти.
По тестам, структуры данных на B-деревьях занимают на 50-80% меньше места, по сравнению с красно-чёрными деревьями. В таблице показано среднее количество байт на элемент в контейнерах set/map разного типа. К примеру, стандартный контейнер set<int32_t> создаёт оверхед 16 байт на каждый из множества маленьких элементов, в то время как альтернативный контейнер btree_set<int32_t> создаёт оверхед всего по 1 байту на элемент.
| Тип |
Вставка |
B-Tree (32-bit) |
Red-Black (32-bit) |
B-Tree (64-bit) |
Red-Black (64-bit) |
| set<int32_t> |
sorted |
4.19 |
20.00 |
4.40 |
40.00 |
|
random |
4.90 |
20.00 |
5.15 |
40.00 |
| set<int64_t> |
sorted |
8.39 |
24.00 |
8.80 |
40.00 |
|
random |
9.96 |
24.00 |
10.47 |
40.00 |
| set<string> |
sorted |
24.57 |
40.00 |
33.60 |
64.00 |
|
random |
29.49 |
40.00 |
40.74 |
64.00 |
| map<int32_t, void*> |
sorted |
8.39 |
24.00 |
8.80 |
48.00 |
|
random |
9.96 |
24.00 |
10.47 |
48.00 |
| map<int64_t, void*> |
sorted |
12.60 |
28.00 |
13.20 |
48.00 |
|
random |
15.16 |
28.00 |
15.92 |
48.00 |
| map<string, void*> |
sorted |
28.67 |
44.00 |
38.16 |
72.00 |
|
random |
34.49 |
44.00 |
46.53 |
72.00 |
На некоторых больших контейнерах есть ещё и выигрыш в скорости доступа за счёт более эффективного использования кэша. На графике показано среднее время выполнения вставки, в зависимости от размеров контейнера. 
Специально для "российских друзей" автор библиотеки пояснил, что не подписывал ось Y, потому что конкретное время выполнения операции зависит от используемого оборудования. В данном случае на 10 млн элементов операция занимает 1,6 микросекунды на красно-чёрных деревьях, против 400 наносекунд на B-деревьях. Компьютер Intel Xeon CPU E5-1650 @ 3.20GHz with L1=32K, L2=256K, L3=12M.Разработчик предупреждает об отличии cpp-btree от стандартных контейнеров: поскольку любые операции вставки и удаления узлов в B-дерево аннулируют существующие итераторы, так что в случае необходимости нужно использовать безопасные версии.
Ссылки по теме
