Database storage structures

Methods

Heaps

Heaps are insert inefficient, records at bottom of heap. Retrieval inefficient because searching is linear. Deletion requires a mark to be placed, when they are deleted the heap needs resorting. File occupancy is typically 40-60%.

Hash Buckets

Calculate where the record is stored based on fields in the record. The has functions ensure even spread of data. Collisions are possible so detection and restoration is required.

B+ Trees

These are the most used in practice. They have a dynamic indexing system. The index is full so file does not have to be ordered.