DBMS Storage & Indexing

Storage Hierarchy (Fastest to Slowest)

Main Memory > Flash Memory > Magnetic Disk > Tape

Heap File

Records are stored in any order

Sorted File

Records are stored sorted by a search key

Hashed File

Hash function determines record placement

Fixed-Length Record

All fields are the same size

Variable-Length Record

Fields differ in size; offsets used for access

Page (in DBMS)

Unit of data transfer between disk and memory

Blocking Factor

Number of records per page = floor(page size / record size)

Buffer Pool

Caches pages in memory for quick access

Common Buffer Replacement Policies

LRU, Clock, MRU

Index

Data structure for fast lookup on search key

Primary Index

Index on primary key (unique)

Secondary Index

Index on non-primary or non-unique attributes

Index Alternative 1

Data entry stores full record

Index Alternative 2

Data entry stores pointer (RID) to record

Index Alternative 3

Data entry stores key + list of RIDs (for duplicates)

Clustering Index

Data file is physically ordered by the index key

Unclustered Index

Data file order does not match index key order

Dense Index

Has one entry per data record

Sparse Index

Has one entry per page (only works with sorted data files)

B+ Tree Index

Multi-level balanced tree; leaf nodes store all data entries

B+ Tree Leaf Nodes

Contain actual data entries and are linked for range scans

B+ Tree Internal Nodes

Contain only keys and child pointers

Hash Index

Uses a hash function to map keys to buckets

Hash Index Use Case

Only supports equality search, not range queries

Extendible Hashing

Hash index with a directory that grows and shrinks

Linear Hashing

Hash index without directory; grows gradually

Seek Time

Time to move disk arm to correct track

Rotational Delay

Time for desired sector to rotate under read head

Transfer Time

Time to actually read/write the data

Index Usage for Equality Queries

Hash or B+ Tree

Index Usage for Range Queries

B+ Tree only

Best Index for Sorting

Clustered B+ Tree

Best Index for Heavy Inserts

Hash Index