Fundamental access methods (reminder - introduction)
external access cost (I/Os) should be lessened when querying data
two ways :
- indexing
- indexes are built as trees whose nodes and leaves contain “entries” i.e. pairs (value, block address) for lower nodes or data
- looking for a given value ? go down the tree
- a node has a maximum entry capacity ? height of the tree
- hashing
- data block address is the result of a computation on the data value
- this computation should be dynamic if data volume vary
- data structures needed should be light to stick into main memory