TLink-Tree: Main Memory Index Structure with Concurrency Control and Recovery

J. Lindström (Finland)


index, data structures, database systems, main-memory, cache-conscious


While B+trees are the most popular index structure for disk databases, the T-Tree has been widely accepted as a promising index structure for main memory databases. For over two decades the speed of CPUs has increased faster than the speed of the main memory. Therefore, the speed gap of the CPU and memory has rapidly become steeper, and memory access has become the new bottle neck in databases. In this paper we explore concurrency control and recovery in a new index structure Tlink -tree which enhances the cache usage, reduces the number of ro tate operations and the overhead required for balancing the tree by delayed split and deletion.

Important Links:

Go Back