Compression can sometimes improve performance by making more of the data available to the processors faster. We consider the compression of integer keys in a B+-tree index. For this purpose, systems such as IBM DB2 use variable-byte compression over differentially coded keys. We revisit this problem with various compression alternatives such as Google's VarIntGB, Binary Packing and Frame-of-Reference. In all cases, we describe algorithms that can operate directly on compressed data. Many of our alternatives exploit the single-instruction-multiple-data (SIMD) instructions supported by modern CPUs. We evaluate our techniques in a database environment provided by Upscaledb, a production-quality key-value database. Our best techniques are SIMD accelerated: they simultaneously reduce memory usage while improving single-threaded speeds. In particular, a differentially coded SIMD binary-packing techniques (BP128) can offer a superior query speed (e.g., 40 better than an uncompressed database) while providing the best compression (e.g., by a factor of ten). For analytic workloads, our fast compression techniques offer compelling benefits. Our software is available as open source.
There has been much research dedicated to improving the performance of tree data structures. For example, cache-conscious trees can reduce the number of cache misses to improve performance @cite_1 @cite_0 . In particular, @cite_0 propose the Cache Sensitive T-Trees (CST-Trees).
@cite_0 @cite_1
2145148249 2127542829
Researchers have modified existing index structures into ones optimized for CPU cache performance in main memory database environments. A Cache Sensitive B+-Tree is one of them. It is designed to minimize the impact of cache misses for B+-Trees and it has been known to be more effective than other types of main memory index structure including T-Trees. In this paper, we introduce a Cache Sensitive T-Tree (CST-Tree) and show how T-Trees can also be redesigned to be cache sensitive. We present an experimental performance study which shows that our Cache Sensitive T-Trees can outperform the original T-Trees and Cache Sensitive B+-Trees on average 65 percent and 17 percent, respectively. The performance of in-memory databases is significantly affected by the number of data blocks fetched from memory into the processor-resident cache. In recent years, various tree-based indexes have been proposed for main memory databases. A common assumption in the analysis of these indexes is that there is no data in the cache that can be reused between key lookups, i.e. the system has a cold cache for each lookup. In practice, though, the ?temperature? of the cache is strongly dependent on the application. For example, a warm cache is typical for OLTP applications that query the same index over and over with little computation in between lookups. In this paper, we present a comparative study of the cache behavior of various B+-tree-based indexes which shows that none of them performs best in all cases. Also, we propose a lightweight technique for improving the cache behavior of any B+-tree based index that performs best in all settings.