bbtree README

README проекта с github.com/XiangpengHao/bbtree. Одним файлом markdown: README.md.

bbtree

crates.io docs.rs
test miri sanitizer DST fuzzing verification

B-trees are by far the most important access path structure in database and file systems. — Jim Gray

bbtree is by far the fastest btree (ordered map):

  1. 5x faster than std's BTreeMap at single thread, 12x faster than crossbeam-skiplist at 96 threads.
  2. 30% lower memory usage, 5x lower p99 latency.
  3. Zero dependencies, no_std compatible.
  4. unsync::BBTreeMap is a drop-in replacement for std's BTreeMap/BTreeSet.
  5. Production-ready by formal verification, model checking, deterministic simulation, fuzzing, and lots of testing.
  6. Brought to you by decades of database research and careful curation by Xiangpeng Hao.

bbtree vs other concurrent maps, get throughput at 96 threads

Checkout how it works at bbtree.xiangpeng.systems.

Usage

cargo add bbtree

Concurrent bbtree

use bbtree::BBTreeMap;

let map = BBTreeMap::new();

std::thread::scope(|scope| {
    scope.spawn(|| map.insert(1_u64, 10_u64));
    scope.spawn(|| map.insert(2, 20));
});

assert_eq!(map.get_copied(&1), Some(10));
assert_eq!(map.read(&2, |_, value| value + 1), Some(21));
assert_eq!(map.get_many_copied([&1, &2, &3]), [Some(10), Some(20), None]);

Single thread

use bbtree::unsync::BBTreeMap;

let mut map = BBTreeMap::new();
map.insert(1, "one");
map.insert(2, "two");
assert_eq!(map.get(&1), Some(&"one"));

Agent's guide

  1. Implement InlinkeKey trait for best performance, check how String and Vec implement it.
  2. Consider using batching api if semantically appropriate.
  3. Create an issue here if you see any performance regression.

license

Licensed under either of Apache License, Version 2.0 or MIT license, at your option; LICENSE holds both texts.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in bbtree by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

bbtree (XiangpengHao/bbtree)

Ищем в базе…

667 ·GitHub
Что это такое?bbtree — это библиотека на Rust, которая реализует конкурентную упорядоченную структуру map (B-дерево). Её авторы заявляют, что это самая быстрая из доступных реализаций: в 5 раз быстрее BTreeMap из std в одном потоке и в 12 раз быстрее crossbeam-skiplist при 96 потоках.
Это библиотека, которую я добавляю в свой проект, или отдельная база данных?Это крейт (библиотека) на Rust, а не самостоятельный сервер или база данных. Он предоставляет конкурентный BBTreeMap для многопоточного использования и вариант unsync::BBTreeMap для однопоточного.
Как мне подключить её к проекту на Rust?Добавьте bbtree как зависимость Cargo, затем используйте либо конкурентный BBTreeMap для многопоточных нагрузок, либо unsync::BBTreeMap как прямую замену BTreeMap и BTreeSet из std.
Тянет ли она за собой внешние зависимости?Нет. У неё нет зависимостей, и она совместима с nostd, поэтому может работать в ограниченных или встраиваемых средах без стандартной библиотеки.
Что нужно сделать, чтобы добиться от неё максимальной производительности?Для максимальной производительности с собственными типами ключей самостоятельно реализуйте трейт InlinkeKey по образцу того, как это сделано для String и Vec. Также стоит рассмотреть API пакетной обработки (batching), если он подходит под вашу нагрузку.
Насколько bbtree действительно быстрее альтернатив?В README заявлено: в 5 раз быстрее BTreeMap из std в одном потоке, в 12 раз быстрее crossbeam-skiplist при 96 потоках, с использованием памяти на 30% меньше и задержкой p99 в 5 раз ниже.
Как проверяется корректность такой конкурентной структуры данных?В проекте заявлено, что он готов к промышленной эксплуатации благодаря формальной верификации, проверке моделей (model checking), детерминированной симуляции, фаззингу и обширному тестированию.
Могу ли я просто заменить свой существующий BTreeMap на bbtree?Да, вариант unsync::BBTreeMap задуман как прямая замена BTreeMap и BTreeSet из std в однопоточном коде.
Какие есть похожие проекты?learned_index_lab, concurrentqueue, pgrust, kividb, phpredis, memcached, goose, dragonfly
Автор
XiangpengHao
Размер
3.7 MB
Звёзды
667
Возраст
1 мес
Коммиты · 90 дней