검색 상세

COB+-트리에 기반한 인덱스 노드 압축과 질의 처리 기법

Index Node Compression and Query Processing Techniques based on COB+-tree

초록/요약

The effectiveness of query processing techniques on in-memory index data structure draws recently more and more attention, especially based on an compressed index. Index node compression improves data locality of index structure, decrease memory references. It makes node group sizes are different. However, the side effect of it is we cannot perform binary search on it. And decompressing can increase computational overhead. The contribution of this paper is three-fold. Firstly, we present a COB+-tree (Compression-Oriented CSB+-tree) data structure, which reduces the number of the second-level cache misses and the translation lookaside buffer misses. Secondly, we describe a fine description of index compressing mechanisms. Finally, by adopting partial decompressing technique, we can improve query processing performance on a COB+-tree. The experimental results show that the COB+-tree can improve the performance of query processing.

more

목차

ABSTRACT 1
TABLE OF CONTENTS 2
LIST OF FIGURES 4
LIST OF TABLES 5
CHAPTER 1. Introduction 6
CHAPTER 2. Cache Conscious 11
2.1 Cache Behavior 11
2.2 Cache-Sensitive B+-trees 12
2.3 T-tree and its variants 13
CHAPTER 3. Page Conscious 15
3.1 the TLB miss 15
3.2 Memory based BD-trees and CPSS-trees 16
CHAPTER 4. The COB+-tree 17
4.1 Data Structure 17
4.2 Efficient Random Access 18
CHAPTER 5. Index Compression for COB+-tree 20
5.1 Index Compression Overview 20
5.2 Delta encoding in COB+-tree 21
5.3 Order Preserving Key Compression for COB+-tree 23
CHAPTER 6. Cost Analysis 25
6.1 Cache and TLB Miss Model 26
CHAPTER 7. Performance Evaluation 27
7.1 Experimental Setup for Index Compressing 27
7.2 Experimental Setup for Processing Performance 28
7.3 Implementation Details 29
7.4 Experimental Result 29
CHAPTER 8. Conclusions and Future work 35
References 36

more
반출 Meta View 목록