Multi Key Index

Last updated Nov 8, 2022 Edit Source

Motivation: we want to be able to have efficient queries on multiple attributes SELECT * WHERE DEPT = "TOY" AND SAL > 50

Build index on y and ax iteratively until each partition contains at most 2 records:

Issues:

• Records may not be allocated into the cells evenly depending on the partitioned ranges: result in overflows or inefficient use of space

Idea: combine the hash value of each key from hash index to form a single index.