Disk Addressing

A modern hard disk drive contains billions of sectors, each holding a small piece of data. When your database needs to read a specific customer's record or write a transaction log entry, the system must identify the exact physical location among these billions of possibilities. Disk addressing is the mechanism that makes this possible.

Why Disk Addressing Matters for Database Systems:

Database performance fundamentally depends on efficient disk addressing:

• Index lookups translate key values to disk addresses for record retrieval
• Query execution plans are optimized based on understanding access patterns
• Buffer pool management uses addresses to track which pages are cached
• Write-ahead logging depends on knowing where log records are persisted
• Free space management tracks which addresses are available for new data

This page examines how disk addressing works at every level—from the low-level hardware translation to the high-level abstractions databases employ.

Cylinder-Head-Sector (CHS) addressing was the original method for specifying disk locations, directly reflecting the physical structure of the drive. While obsolete for modern systems, understanding CHS provides insight into why LBA was developed and how legacy systems operated.

The CHS Triplet:

An address in CHS format consists of three components:

• Cylinder (C) — Which concentric track position (determines arm position)
• Head (H) — Which recording surface (determines active head)
• Sector (S) — Which sector within the track (determines rotation position)

Example: CHS (1000, 4, 32) means:

• Position the arm at cylinder 1000
• Activate head 4 (5th surface, since numbering starts at 0)
• Read/write sector 32 on that track

CHS to Physical Mapping:

Physical Location = f(Cylinder, Head, Sector)
Arm Position determined by Cylinder
Active Head selected by Head number  
Rotational Position determined by Sector number

*Note: Sector numbering in CHS typically started at 1, not 0, limiting practical maximum to 63.

Why CHS Failed:

1. Rigid Capacity Limits — BIOS constraints created hard 8.4 GB barrier
2. Zone Bit Recording Incompatibility — CHS assumed constant sectors per track, but ZBR varies sector count
3. Defect Handling Complexity — Bad sectors couldn't be transparently hidden
4. Geometry Knowledge Required — Host needed to know exact physical layout
5. Inefficient Space Utilization — Couldn't optimize for ZBR geometry

The CHS Legacy:

Despite obsolescence, CHS influenced:

• MBR (Master Boot Record) partition table format
• Boot sector loading procedures
• Terminology still used in disk discussions
• Some legacy embedded systems still use CHS-like addressing

Logical Block Addressing (LBA) replaced CHS as the universal disk addressing method. LBA presents the disk as a simple linear array of sectors, numbered from 0 to N-1.

The LBA Abstraction:

Disk = [Sector 0][Sector 1][Sector 2]...[Sector N-1]

Where N is the total number of sectors:

• N = Total Capacity / Sector Size
• For a 10 TB drive with 4K sectors: N = 10×10¹² / 4096 ≈ 2.44 billion sectors

Benefits of LBA:

1. Simple Linear Model — Just one number identifies each sector
2. No Geometry Knowledge Required — Host doesn't need drive internals
3. Transparent ZBR Support — Drive handles variable sectors per track internally
4. Transparent Defect Management — Bad sectors remapped without host awareness
5. Large Address Space — 48-bit LBA supports 128 PB; 64-bit supports 8 ZB

LBA Commands:

Modern storage interfaces use LBA-based commands:

READ (LBA, Count):

• Read 'Count' consecutive sectors starting at 'LBA'
• Returns data or error status

WRITE (LBA, Count, Data):

• Write 'Data' to 'Count' consecutive sectors starting at 'LBA'
• Returns success or error status

TRIM/UNMAP (LBA, Count):

• Inform drive that sectors are no longer needed
• Allows drive to optimize (important for SSDs, some HDDs)

VERIFY (LBA, Count):

• Verify sectors are readable without transferring data
• Used for media scanning and integrity checks

Understanding the mathematical relationship between CHS and LBA illuminates how disk addressing evolved and enables working with legacy systems that still expose CHS interfaces.

CHS to LBA Formula:

For a drive with geometry (C_max, H_max, S_max):

LBA = (C × H_max × S_max) + (H × S_max) + (S - 1)

Where:

• C = Cylinder number (0 to C_max - 1)
• H = Head number (0 to H_max - 1)
• S = Sector number (1 to S_max, since CHS sectors start at 1)

Example Calculation:

Drive geometry: 1000 cylinders, 16 heads, 63 sectors per track

CHS (500, 8, 32) → LBA:

LBA = (500 × 16 × 63) + (8 × 63) + (32 - 1)
LBA = 504,000 + 504 + 31
LBA = 504,535

LBA to CHS Reverse Conversion:

S = (LBA mod S_max) + 1
H = (LBA / S_max) mod H_max
C = (LBA / S_max) / H_max

LBA Order Implies Access Pattern:

The CHS-to-LBA formula reveals the intended access order:

1. First, exhaust sectors on current track (S changes, H and C constant)
2. Then, switch to next head (H increments, C constant)
3. Finally, seek to next cylinder (C increments)

This produces the optimal access pattern: sectors → heads → cylinders

Why This Matters:

Sequential LBA access (0, 1, 2, 3...) naturally follows this pattern:

• Minimal seeks (cylinders change least frequently)
• Head switches preferred over seeks
• Rotational latency is the primary delay for sequential access

The drive's controller firmware maintains complex translation tables and algorithms to convert LBA addresses into actual physical locations. This internal translation handles ZBR, defect management, and performance optimization.

Translation Layers:

Host Request (LBA) 
    ↓
[Interface Controller]
    ↓
[LBA Translation Engine]
    ↓
[Defect Remapping Check]
    ↓
[Zone Determination]
    ↓
[Physical CHS Calculation]
    ↓
[Servo Position Commands]

Zone Bit Recording Translation:

With ZBR, the mapping is no longer a simple formula. The drive maintains a zone table:

Defect Remapping in Translation:

The translation engine also handles grown defects:

1. Before returning physical address, check G-List
2. If LBA is in defect list, redirect to spare sector
3. Spare sector may be in different zone/cylinder
4. This can introduce unexpected seek for 'sequential' access

Firmware Optimization:

Modern drives may use more sophisticated mapping for optimization:

• Shingled zones may require different translation rules
• Media cache areas may temporarily hold writes
• Interleaving patterns may optimize for rotational latency
• Write pointer tracking for SMR zones

Partition tables divide the disk's LBA space into non-overlapping regions, each addressable as an independent logical volume. Understanding partition addressing is essential for database deployment.

MBR Partition Table (Legacy):

The Master Boot Record format uses 32-bit LBA addresses:

• Maximum addressable: 2³² sectors = 2 TB (512B sectors) or 16 TB (4K sectors)
• 4 primary partitions maximum
• Extended partitions allow more via linked list

MBR Partition Entry Structure:

| Bootable | Start CHS | Type | End CHS | Start LBA | Size (sectors) |
| 1 byte   | 3 bytes   | 1 byte| 3 bytes | 4 bytes   | 4 bytes        |

GPT Partition Table (Modern):

GUID Partition Table addresses modern needs:

• 64-bit LBA addresses (supports yottabyte-scale storage)
• 128 or more partition entries
• Backup copy at end of disk
• CRC checksums for integrity
• Default alignment at 1 MiB (LBA 2048 for 512B sectors)

GPT Partition Entry Structure:

| Partition Type GUID | Unique GUID | First LBA | Last LBA | Attributes | Name |
| 16 bytes            | 16 bytes    | 8 bytes   | 8 bytes  | 8 bytes    | 72 bytes |

Address Calculation for File Systems:

When a file system is created on a partition:

File_System_LBA = Partition_Start_LBA + Relative_LBA_within_Partition

For a database file at relative sector 10000 on a partition starting at LBA 2048:

Absolute_LBA = 2048 + 10000 = 12048

File systems add another addressing layer between applications and raw LBA access. Understanding this layer clarifies how database files map to disk locations.

File System Address Components:

1. Inode/File ID — Identifies the file
2. Block Number — Position within the file
3. Block Offset — Byte position within the block

Block Allocation:

File systems allocate disk space in blocks (clusters):

• Block Size: Typically 4KB, 8KB, 16KB, or larger
• Block Number: Sequential numbering within the file system
• Block Bitmap: Tracks which blocks are allocated

Extent-Based Allocation (Modern):

Modern file systems (ext4, XFS, NTFS) use extents for efficiency:

Extent = { Start_Block, Length }

A file might be described by:

• Extent 1: Start at block 10000, length 1000 blocks
• Extent 2: Start at block 50000, length 500 blocks

This is more efficient than tracking individual blocks.

Fragmentation and Address Locality:

File system block allocation affects address locality:

Contiguous Allocation:

File blocks: 1000, 1001, 1002, 1003, 1004 (contiguous)
LBAs: 8000, 8001, 8002, 8003, 8004 (sequential)
Result: Efficient sequential I/O

Fragmented Allocation:

File blocks: 1000, 5000, 2500, 8000, 3000 (scattered)
LBAs: 8000, 40000, 20000, 64000, 24000 (random)
Result: Each read requires a seek

Database Files and Fragmentation:

Databases typically:

• Pre-allocate large contiguous extents
• Grow files in large chunks to maintain contiguity
• Use raw devices or direct I/O to bypass file system caching
• May use file system features to ensure contiguous allocation

Databases implement their own addressing schemes on top of file system primitives, organizing data into pages (blocks) with specific structure and addressing conventions.

Database Page Addressing:

Most relational databases organize storage around pages:

• Page Size: 4KB (MySQL), 8KB (PostgreSQL, SQL Server), 16KB (Oracle)
• Page Number: Sequential identifier within a data file or tablespace
• Page Types: Data pages, index pages, free space pages, header pages

Page Address Structure:

(File_ID, Page_Number) → Physical Page

Where:

• File_ID identifies the data file among potentially many
• Page_Number identifies position within that file
• Offset = Page_Number × Page_Size

Index Pointers:

Indexes store pointers to data locations:

B-tree Leaf Entry: (Key_Value, Row_Pointer)
Row_Pointer: (Page_Number, Slot_Number)

When an index lookup finds a key, the pointer directs the system to:

1. The specific page containing the row
2. The slot within that page (for slotted page formats)

Buffer Pool and Page Addressing:

The database buffer pool caches pages in memory using page addresses:

Buffer_Pool[hash(File_ID, Page_Number)] → Page_Frame

When a page is requested:

1. Hash the page address
2. Check if page is in buffer pool
3. If hit: Return cached page
4. If miss: Read page from disk into a free frame, then return

Example: PostgreSQL CTID

PostgreSQL uses CTID (Current Tuple ID) as row address:

CTID = (block_number, tuple_index)

• Block_number: Page within the table file
• Tuple_index: Offset within the page's item pointer array