Please enable JavaScript.
Coggle requires JavaScript to display documents.
Bit Indexes - Coggle Diagram
Bit Indexes
Bit Map Index
Motivation
-
-
Worse if attribute is Boolean, domain is 3: yes, no, NULL
many duplicates, weird B+ Tree
Solution
build 3 bitmap arrays, one for each value
ith bit in each bitmap (array) = ith tuple, map to rid
-
-
COUNT: index-only strategy, quick
-
Storage
-
1 bitmap / file, can be compressed
-
Space efficient than B+ Tree: per tuple
1 + #distinct value < data entry size in B+ tree (key-size + rid-size)
Bit Slice Index
-
Solution
-
1 bit = 1 slice = 1file, 1 more for NULL
construct and store in result bitmap, no need to go to heap file
-
if look for 0 and have 1, put 0 in result
if look for 1 and have 0, put 1 in result
from high bit to low bit, else consider next bit slice
Aggregates (e.g. SUM)
count # of 1s in slice 16, * 2^16 ...
-
-