Delete operation on Multi ART

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

	switch ((uint64_t)ret) {
	case 0: // key existed
	mass_node_unlock(n);
	return 0;
	case 1: // key inserted
	mass_node_unlock(n);
	return 1;
	case -1: { // need to create a deeper layer
	create_new_layer(n, key, len, off, val);
	mass_node_unlock(n);
	return 1;
	}
	case -2: { // mass_node is full, need to split and promote
	uint64_t fence = 0;
	mass_node *n1 = mass_node_split(n, &fence);
	assert(fence);
	uint64_t cur = get_next_keyslice(key, len, off);
	// equal is not possible
	if (mass_compare_key(cur, fence) < 0)
	assert((uint64_t)border_mass_node_insert(n, key, len, off, val, 0 /* is_link */) == 1);
	else
	assert((uint64_t)border_mass_node_insert(n1, key, len, off, val, 0 /* is_link */) == 1);

	mass_tree_promote_split_mass_node(mt, n, fence, n1);
	return 1;
	}
	default: // need to go to a deeper layer
	mass_node_unlock(n);
	r = (mass_node *)ret;
	// if we need to advance to next layer, then key offset will not exceed key length
	off += sizeof(uint64_t);
	goto again;
	}

	char key = (alloc)(16);
	key[0] = 8;
	(uint64_t )(key + 1)= rng_next(&r);
	assert(adaptive_radix_tree_put(ta->tree.art, (const void *)(key + 1), 8) == 0);

uncp / aili Goto Github PK

aili's Introduction

aili

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

Algorithms

Have a Try

Benchmark

Benchmark Multi ART

Other

References

aili's People

Contributors

Stargazers

Watchers

Forkers

aili's Issues

Recommend Projects

Recommend Topics

Recommend Org