aili

the fastest in-memory index in the East

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)

Version

see Version.md for brief info
see ChangeLog.md for detail info

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 可以在一台96核的机器上使用64个线程跑到单机1亿tps。

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

bobbyzhu/aili