A library that provides various concurrent algorithms for in-memory index, aims to achieve extremely FAST speed, but just for EXPERIMENT and FUN.
- Palm Tree (
palm/
) - Blink Tree (
blink/
) - Mass Tree (
mass/
) - Adaptive Radix Tree (
art/
) - Height Optimized Trie (
hot/
) (developing)
# thread_num thread_key_number
./run.sh palm 4 100 # test palm tree
./run.sh blink 4 100 # test blink tree
./run.sh mass 4 100 # test mass tree
./run.sh art 4 100 # test art tree
Multi ART is capable of reaching 100 million insert per second on a 96-core machine using 64 threads.
- Checkout
example/
for examples - Follow my 知乎专栏 for blogs about this repository
- Open an issue if you have any problem
- Palm Tree : Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors
- Mass Tree : Cache Craftiness for Fast Multicore Key-Value Storage
- Blink Tree : Efficient Locking for Concurrent Operations on B-Trees
- Prefetch B+ Tree : Improving Index Performance through Prefetching
- Prefix B Tree : Prefix B-Trees
- B* Tree : The Art of Computer Programming, Volume 3, Chapter 6
- Adaptive Radix Tree : The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases