art

ART

Designed for main memory index:

1. Read optimization
2. Write exclusion
3. CPU Cache & Pipeline friendly
4. Saving memory space

Introduction

Why Adaptive Radix Tree

Main memory capacities have grown up to a point where most databases fit into RAM. For main-memory database systems, index structure performance is a critical bottleneck. Traditional in-memory data structures like balanced binary search trees are not efficient on modern hardware, because they do not optimally utilize on-CPU caches. Hash tables, also often used for main-memory indexes, are fast but only support point queries.

Adaptive Radix Tree overcomes these shortcomings.

You could find more details in <The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases>.

What's more, one important invariant of ART is that every insertion/deletion order results in the same tree because there are no re-balancing operations. Which means it's easier to implement thread-safe structure.

Why Adaptive Radix Tree is not popular

It was proposed for the first time in 2010, it's too new for a memory index structure.

There is no mature implementation in present.

Limitation

Platform

Only supports X86-64 which has CMPXCHG16B feature (only early processors laked it):

16bytes value could be accessed atomically.

Cannot mix pointer and value in inner node

Go's invalid pointer checking will find the invalid pointer(value). Although we can disable it, it may cause unpredictable collapse.

Acknowledge

1. ART index, UncP/aili

2. ART based on <The ART of Practical Synchronization> flode/ARTSynchronized

Thanks for their contribution!