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/)

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

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