How Tables and indexes stored on Disk

Introduction

This article delves into the structured manner in which tables and indexes are stored on disks in database systems. This understanding is pivotal for database optimization, impacting the efficiency of data access and manipulation.

Tables Storage

Data Pages

• Definition: Tables are stored in units known as "data pages" or "blocks."
• Content: Each page typically holds a fixed number of rows. The exact number depends on the row size and page size, which is often 4 KB or 8 KB.
• Organization: These pages are systematically arranged into a file or a set of files on the disk.

Example:

Consider a table with rows of 1 KB each. On a 4 KB page, up to four rows can be stored. If the table has 1000 rows, it would occupy at least 250 pages.

Row Format

• Storage Types: Rows can be stored in fixed-length or variable-length formats.
• Detail: Each row consists of its column values.

Table Metadata

• Information Stored: Details about the table structure, including column names, data types, and constraints.
• Location: This information is usually stored in a system catalog or a metadata table.

File Organization

• Types:
  1. Heap: An unordered storage of rows.
  2. Clustered Index: Rows are stored in the order of the primary key.
  3. Partitioned: The table is divided into smaller, more manageable segments.

Indexes Storage

B-tree Indexes

• Structure: A balanced tree consisting of root, internal, and leaf nodes.
• Function: Leaf nodes contain index entries with a key value and a pointer to the corresponding row.
• Commonality: This is the most commonly used index structure.

Bitmap Indexes

• Mechanism: Uses a bitmap for each key to indicate the presence or absence of a value.
• Efficiency: Particularly effective for columns with a low number of distinct values.

Hash Indexes

• Function: Utilizes a hash function to create a hash value for each key.
• Purpose: These hash values facilitate quick data location during searches.

Index Metadata

• Content: Information about the index, like indexed columns and index type.
• Storage: Stored in the system catalog, similar to table metadata.

Storage

• Separation: Indexes are stored separately from the table data.
• Extent: They may cover multiple pages and files, varying in size.

Physical Storage

Disk Files

• Medium: Both tables and indexes are stored as files on the disk.

File System or Raw Devices

• Management: These files might be managed by the file system or stored on raw devices, depending on the DBMS.

I/O Operations

• DBMS Role: The DBMS handles read/write operations, focusing on minimizing disk I/O, caching, and maintaining ACID properties.

Conclusion

Understanding the storage mechanisms of tables and indexes on disk is critical for optimizing database performance. This knowledge aids in making informed decisions about data organization and access strategies.