С++ библиотека от Google с контейнерами map и set на B-деревьях

Один из сотрудников 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

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

Разработчик предупреждает об отличии cpp-btree от стандартных контейнеров: поскольку любые операции вставки и удаления узлов в B-дерево аннулируют существующие итераторы, так что в случае необходимости нужно использовать безопасные версии.

via Google Open Source Blog