5.2 Tree-Structured Indexes

5.2 Tree-Structured Indexes

Now, let?s go back to the original unindexed table for a minute. If the table is kept in sorted order, then I use a binary search to locate a particular row or a subset of the rows based on the columns used for sorting. If you have ( n ) rows in the table, then the binary search will take at most log ₂ ( n ) disk reads to locate a row. The trade-off will be in keeping the tables in order when new rows are inserted. The only thing SQL-92 says about an inherent sorting order is that all NULL s must sort together either before or after all values.

Just as we viewed the simple index as putting a linear search into a persistent data structure, we can think of a tree-structured index as putting a binary (or n -ary) search into a persistent data structure.

There are many different types of tree-structured indexes, but they all have the same motivation. As a simple index gets bigger and bigger, it starts to require longer and longer search times. The obvious solution is to build a sparse index on the original index, in which the sparse index points to the pages of the original index. Then build another sparse index on the index to the original index, and so forth. When this process stops, we have a tree structure that starts at a root node. In practice, all these layers of indexing are kept in...

< Previous Excerpt Next Excerpt >

Purchase This Book

Joe Celko's Data and Databases: Concepts in Practice

TABLE OF CONTENTS

5.2 Tree-Structured Indexes

Contact Preferences

This is embarrasing...

Customize Your GlobalSpec Experience

Select Your Free Newsletters

Industry Newsletters

Select Your Free Product Alerts

This is embarrasing...