Index Structures for Data Warehouses 数据库结构指数索引

1　Introduction
　1.1 Goals
　1.2 Outline
2　State of the Art of Data Warehouse Research
　2.1 Introduction
　2.2 Traditional Transaction-Oriented Systems
　2.3 Data Warehouses for Decision Support
　2.4 OLAP Vs.OLTP
　2.5 Accelerating Query Speed
　　2.5.1 Denormalized Schemas
　　2.5.2 Materialized Views
　　2.5.3 No Locking
　　2.5.4 On-line Aggregation
　　2.5.5 Index Structures
　2.6 Summary
3　Data Storage and Index Structures
　3.1 Introduction
　3.2 Memory Hierarchy
　3.3 Mechanics of Disks
　3.4 Data Space and Queries
　　3.4.1 Data Space
　　3.4.2 Queries
　3.5 Tree-Based Indexing
　　3.5.1 Top-Down, Bottom-Up, and Bulk Loading
　　3.5.2 Point Quadtrees
　　3.5.3 kd-tree
　　3.5.4 kdb-tree
　　3.5.5 R-tree
　　3.5.6 R*-tree
　　3.5.7 Other Relatives of the R-tree Family and Other Tree Structures
　　3.5.8 Generic Tree Structures
3.6 Bitmap Indexing
3.6.1 Standard Bitmap Indexing
3.6.2 Multi-component Equality Encoded Bitmap Index
3.6.3 Range-Based Encoding
3.6.4 Multi-component Range-Based Encoding
3.6.5 Other Compression Techniques/Combination of Bitmaps and Trees
　3.7 Arrays
　3.8 Summary
4　Mixed Integer Problems for Finding Optimal Tree-Based Index Structures
　4.1 Introduction
　4.2 Optimization Problem Parameters
　4.3 Mapping into a Mixed Integer Problem
　4.4 Problem Complexity
　4.5 Model Evaluation
　4.6 Summary
5　Aggregated Data in Tree-Based Index Structures
　5.1 Introduction
　5.2 “Fit for Aggregation” Access Method
　5.3 Materialization of Data
　5.4 Modified Operations
　　5.4.1 Insert Operation
5.4.2 Delete Operation
5.4.3 Update Operation
5.4.4 Creating Index Structures，Bottom-Up Index Structures
　　5.4.5 Point Query Algorithm
　　5.4.6 Range Query Algorithm
　5.5　Storage Cost
　5.6　Height of Tree
　5.7　Overlaps of Regions
　5.8　Experiments
　　5.8.1 Cost Model
　　5.8.2 Physical Index Structure
　　5.8.3 Implementation
　　5.8.4 Generation of Test Data
　　5.8.5 Query Profile
　　5.8.6 Results of Experiments
　5.9　Summary
6　Performance Models for Tree-Based Index Structures
7 Techniques for Comparing Index Structures
8 Conclusion and Outlook
A List of Symbols
B Approximation of PISA Model
Bibliography
Index