Benchmarking a B-tree compression method?

Abstract. The B-tree and its variants have been widely applied in many data management fields. When a com-pression of these data structures is considered, we follow two objectives. The first objective is a smaller index file, the second one is a reduction of the query processing time. In this paper, we apply a compression scheme to fit these objectives. The utilized compression scheme handles com-pressed nodes in a secondary storage. If a page must be re-trieved then this page is decompressed into the tree cache. Since this compression scheme is transparent from the tree operation’s point of view, we can apply various compression algorithms to pages of a tree. Obviously, there are compres-sion algorithms suitable for various data collections, and so, this issue is very important. In our paper, we compare the B-tree and compressed B-tree where the Fast Fibonacci and invariable coding compression methods are applied. Key words: B-tree and its variants, B-tree compression, compression scheme, fast decompression algorithm