aili

the fastest in-memory index in the East（maybe the fastest on this planet）

A library that provides various concurrent algorithms for in-memory index, aims to achieve extremely FAST speed, but just for EXPERIMENT and FUN.

Algorithms

• Palm Tree (palm/)
• B^link Tree (blink/)
• Mass Tree (mass/)
• Adaptive Radix Tree (art/)
• Height Optimized Trie (hot/) (developing)

Have a Try

#              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

Benchmark

Benchmark Multi ART

Multi ART is capable of reaching 100 million insert per second on a 96-core machine using 64 threads.

Other

• Checkout example/ for examples
• Follow my 知乎专栏 for blogs about this repository
• Open an issue if you have any problem

References

• 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
• B^link 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