Joe Celko's Data and Databases: Concepts in Practice
By Joe Celko

5.6 Bit Vector Indexes

5.6 Bit Vector Indexes
FoxPro and Nucleus are two examples of products that use different bitmap schemes, but they have some basic features in common. Imagine an array with table row numbers or pointers on its columns and values for that column on its rows.
If a table row has that value in that position, then the bit is set; if not, the bit is zeroed. A search is done by doing bitwise ANDs, ORs, and NOTs on the bit vectors.
This might be easier to explain with an example of the technique. Assume we have Chris Date?s Parts table, which has columns for the attributes ?color? and ?weight.?
Parts
pno
pname
color
weight
city
?p1?
?Nut?
?Red?
12
?London??Physical row #3
?p2?
?Bolt?
?Green?
17
?Paris??Physical row #4
?p3?
?Cam?
?Blue?
12
?Paris??Physical row #7
?p4?
?Screw?
?Red?
14
?London??Physical row #9
?p5?
?Cam?
?Blue?
12
?Paris??Physical row #11
?p6?
?Cog?
?Red?
19
?London??Physical row #10
The bit indexes are built by using the physical row and the values of the attributes in an array, thus:
INDEX Parts (color)
Rows
1
2
3
4
5
6
7
8
9
10
11
Blue
0
0
0
0
0
0
1
0
0
0
1
Green
0
0
0
1
0
0
0
0
0
0
0
Red
0
0
1
0
0
0
0
0
1
1
0
INDEX Parts (weight)
Rows
1
2
3
4
5
6
7
8
9
10
11
12
0
0
1
0
0
0
Copyright Morgan Kauffmann Publishers 1999 under license agreement with Books24x7
< Previous Excerpt Next Excerpt >
Purchase This Book

UNLIMITED FREE
ACCESS TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: Vacuum Fluorescent Displays

Select Your Free Newsletters

Industry Newsletters

Select Your Free Product Alerts

Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.