Core Concepts of Database Indexing

An index serves as a data structure within a database designed to enhance the speed of data retrieval operations. By organizing references to actual data, it allows for efficient querying without scanning every row in a table. This mechanism significantly reduces I/O overhead for read operations and minimizes CPU usage during data sorting. However, the presence of indexes introduces a trade-off: they consume additional storage space and decrease performance for write operations (INSERT, UPDATE, DELETE) because the database must dynamically maintain the index structure.

Index Structures in MySQL

MySQL supports four primary index structures, each suited for specific use cases:

• B-Tree Index: The default and most widely used index type, suitable for range queries and exact matches.
• Hash Index: Optimized for exact equality comparisons but not for range searches.
• R-Tree Index: Designed for spatial data and geographic information storage.
• Full-Text Index: Utilizes inverted indexes to facilitate efficient text searching within documents.

Unless specified otherwise, standard indexes (including Primary, Unique, and Composite indexes) utilize the B+ Tree structure.

B-Tree vs. B+ Tree

Both B-Tree and B+ Tree are multi-way balanced search trees, but they differ in critical ways that impact database performance.

B-Tree: Both internal and leaf nodes store key values and data pointers. This means useful data can be found early in the traversal. However, this reduces the number of keys a node can hold, potentially increasing tree height and disk I/O.

B+ Tree: Internal nodes act strictly as navigational guides, storing only keys and child pointers. All data records are stored exclusively in the leaf nodes, which are linked sequentially. This structure offers several advantages:

• Lower Disk I/O: Since internal nodes lack data pointers, they can store more keys per block, keeping the tree shallower.
• Stable Query Performance: All queries terminate at leaf nodes, ensuring consistent path lengths.
• Efficient Range Scans: The linked list of leaf nodes facilitates rapid sequential access for range queries.

Logical Index Classifications

Indexes can be categorized logically based on their constraints and column composition:

1. Single-Column Index: An index created on a single table column.
2. Unique Index: Enforces uniqueness on the indexed columns, preventing duplicate values (NULL values are typically allowed).
3. Composite Index: An index created on multiple columns. The order of columns in the definition is significant for query optimization.

Practical Syntax and Operations

To demonstrate index operations, consider the following schema setup:

CREATE DATABASE hr_system DEFAULT CHARSET=utf8mb4;
USE hr_system;

CREATE TABLE `employees` (
  `emp_id` INT(11) NOT NULL AUTO_INCREMENT,
  `emp_name` VARCHAR(50) NOT NULL,
  `department_id` INT(11) NOT NULL,
  PRIMARY KEY (`emp_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE `departments` (
  `department_id` INT(11) NOT NULL AUTO_INCREMENT,
  `department_name` VARCHAR(100) NOT NULL,
  PRIMARY KEY (`department_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Creating and Managing Indexes

Indexes can be created explicitly using the CREATE INDEX statement or modified using ALTER TABLE.

Creating a standard index on a specific column:

CREATE INDEX idx_emp_name ON employees(emp_name);

Viewing existing indexes on a table:

SHOW INDEX FROM employees;

The output will show the primary key index (named PRIMARY) and the newly created idx_emp_name. The Non_unique field indicates whether duplicate values are permitted (0 for unique, 1 for non-unique).

Using ALTER TABLE for index management:

-- Add a composite index
ALTER TABLE employees ADD INDEX idx_name_dept (emp_name, department_id);

-- Add a unique index
ALTER TABLE employees ADD UNIQUE INDEX idx_unique_name (emp_name);

-- Drop an index
DROP INDEX idx_emp_name ON employees;

Index Design Strategies

Effective indexing requires careful consideration of database usage patterns:

• Frequency and Volume: Index tables that are frequently queried and contain large volumes of data. Small tables may not benefit significantly from indexing.
• Column Selection: Prioritize columns appearing in WHERE clauses, JOIN conditions, or ORDER BY clauses.
• Cardinality: Choose columns with high cardinality (many distinct values). Unique indexes offer the highest efficiency because they allow the optimizer to pinpoint a single row.
• Key Length: Shorter index keys require less storage and memory, improving I/O efficiency. If a long column must be indexed, consider using a prefix index.
• Composite Index Optimization: A composite index on columns (A, B, C) can support queries filtering on A, A and B, or A, B, and C. This phenomenon, known as the "Leftmost Prefix" principle, means a single composite index can serve multiple query patterns.