Index families
Index families
Single attribute Multiple attributes Location
m
d
integrated
binary tree
w=2
in memory
broad tree
w~100
in file records
B-tree
~.67dense
updateable
AVL tree
dense,
optimized
trees O(logwn)
hashing
O(1+d )
exact
match
only,
no order
Z-order
Segmenting
points
object
partioning
Bounding
Box
2d
B+-tree
leaf nodes
traversable
Gridding
feature
listing
K-d tree
d levels
repeated
n objects with
m attributes,
d dimensions.
w entries/page
Bertino et al: Indexing Techniques, Kluwer 1997.
R-tree
boxes at each level
R*-tree
boxes optimized
for coverage
R+-tree
BV-tree
region-id
s-K-d tree
add
centroid
space filling
hierarchies
other
signatures
vector
matching
(partial)