{"title":"Indexing","description":null,"content":"Consider a large **Book** of 1000 pages.\n\nSuppose you’re trying to find the page which contains information related to a certain **word**.\n\nWithout an index page, you would have to go through every page, which could take hours or even days.\n\nBut with an index page, you know where to look!\n\nOne you find the right index, you can efficiently jump to that page.\n\nThe index, since it's **sorted** alphabetically and gives page numbers for specific information, saves us from spending too much time flipping through every page.\n\n**Database indexes** work in a similar manner. They guide the database to the exact location of the data, enabling faster and more efficient data retrieval.\n\nIn this article, we'll explore:\n\n- What are database indexes?\n- How do they work?\n- Benefits of using them.\n- Different types of indexes.\n- Which data structure they use?\n- How to use them smartly?\n\n---\n\n# **1. What are Database Indexes?**\n\n\n\nA database index is a super-efficient lookup table that allows a database to find data much faster.\n\nIt holds the indexed column values along with pointers to the corresponding rows in the table.\n\nWithout an index, the database might have to scan every single row in a massive table to find what you want – a painfully slow process.\n\nBut, with an index, the database can zero in on the exact location of the desired data using the index’s pointers.\n\n### How to create Indexes?\n\nHere's an example of creating an index in a MySQL database.\n\nLet's say we have a table named `employees` with the following structure:\n\n\n```sql\nCREATE TABLE employees (\n id INT PRIMARY KEY,\n first_name VARCHAR(50),\n last_name VARCHAR(50),\n email VARCHAR(100),\n department VARCHAR(50),\n salary DECIMAL(10, 2)\n);\n```\n\n\nNow, let's create an index on the `last_name` column to improve the performance of queries that frequently search or sort based on the last name.\n\n\n```sql\n-- Create index on last_name for faster lookups\nCREATE INDEX idx_last_name ON employees (last_name);\n```\n\n\nIn this example, we use the `CREATE INDEX` statement to create an index named `idx_last_name` on the `employees` table. The index is created on the `last_name` column.\n\nAfter creating the index, queries that involve conditions or sorting on the `last_name` column will be optimized. For example:\n\n\n```sql\n-- Query to find employees with last name 'Smith'\nSELECT * FROM employees WHERE last_name = 'Smith';\n```\n\n\nThis query will use the `idx_last_name` index to quickly locate the rows where the `last_name` is 'Smith', avoiding a full table scan.\n\nYou can also create indexes on multiple columns (composite indexes) if your queries frequently involve conditions on multiple columns together. For example:\n\n\n```sql\n-- Create composite index on first_name and last_name\nCREATE INDEX idx_full_name ON employees (first_name, last_name);\n```\n\n\nThis creates a composite index on the `first_name` and `last_name` columns, which can be useful for queries that search or sort based on both columns.\n\n---\n\n# 2. How do Database Indexes Work?\n\nHere's a step-by-step explanation of how database indexes work:\n\n1. **Index Creation**: The database administrator creates an index on a specific column or set of columns.\n2. **Index Building**: The database management system builds the index by scanning the table and storing the values of the indexed column(s) along with a pointer to the corresponding data.\n3. **Query Execution**: When a query is executed, the database engine checks if an index exists for the requested column(s).\n4. **Index Search**: If an index exists, the database searches the index for the requested data, using the pointers to quickly locate the data.\n5. **Data Retrieval**: The database retrieves the requested data, using the pointers from the index.\n\n---\n\n# **3. Benefits of Database Indexes**\n\nDatabase indexes offer several benefits, including:\n\n- **Faster Query Performance**: Indexes can significantly improve query performance especially for large datasets by reducing the amount of data that needs to be scanned.\n- **Reduced CPU Usage**: By reducing the number of rows that need to be scanned, indexes can decrease CPU usage and optimize resource utilization.\n- **Rapid Data Retrieval**: Indexes enable quick data retrieval for queries that involve equality or range conditions on the indexed columns.\n- **Efficient Sorting**: Indexes can also be used to efficiently sort data based on the indexed columns, eliminating the need for expensive sorting operations.\n- **Better Data Organization**: Indexes can help maintain data organization and structure, making it easier to manage and maintain the database.\n\n---\n\n# 4. Types of **Database** Indexes\n\n### Indexes based on Structure and Key Attributes:\n\n- **Primary Index:** Automatically created when a primary key constraint is defined on a table. Ensures uniqueness and helps with super-fast lookups using the primary key.\n- **Clustered Index:** Determines the order in which data is physically stored in the table. A clustered index is most useful when we’re searching in a range. Only one clustered index can exist per table.\n- **Non-clustered or Secondary Index:** This index does not store data in the order of the index. Instead, it provides a list of virtual pointers or references to the location where the data is actually stored.\n\n### Indexes based on Data Coverage:\n\n- **Dense index:** Has an entry for every search key value in the table. Suitable for situations where the data has a small number of distinct search key values or when fast access to individual records is required.\n- **Sparse index:** Has entries only for some of the search key values. Suitable for situations where the data has a large number of distinct search key values.\n\n### Specialized Index Types:\n\n- **Bitmap Index:** Excellent for columns with low cardinality (few distinct values). Common in data warehousing.\n- **Hash Index:** A index that uses a hash function to map values to specific locations. Great for exact match queries.\n- **Filtered Index:** Indexes a subset of rows based on a specific filter condition. Useful to improve query speed on commonly filtered columns.\n- **Covering Index:** Includes all the columns required by a query in the index itself, eliminating the need to access the underlying table data.\n- **Function-based index:** Indexes that are created based on the result of a function or expression applied to one or more columns of a table.\n- **Full-Text Index**: A index designed for full-text search, allowing for efficient searching of text data.\n- **Spatial Index:** Used for indexing geographical data types.\n\n---\n\n# 5. What Data Structure do Indexes use?\n\nMost commonly used data structures that power indexes are B-Trees, Hash Tables and Bitmaps.\n\n### B-Tree (Balanced Tree)\n\n\n\nMost database engines use either a B-Tree or a variation of B-Trees like B+ Trees.\n\nB-Trees have a hierarchical structure with a root node, internal nodes (index nodes), and leaf nodes.\n\nEach node in a B-Tree contains a sorted array of keys and pointers to child nodes.\n\nHere's why they are so well-suited:\n\n- **Self-Balancing:** B-trees ensure that the 'height' of the tree stays balanced even when inserting or deleting data. This ensures `logarithmic time complexity` for insertion, deletion, and searching.\n- **Ordered:** B-trees keep the data sorted, making range queries (\"find all orders between date X and Y\") and inequality comparisons very fast.\n- **Disk-Friendly:** B-trees are designed to work well with disk-based storage. A single node of a B-tree often corresponds to a disk block, minimizing disk access operations.\n\nMany databases use a slightly modified B-tree variant called the B+ tree.\n\nIn a B+ tree, all data values are stored only in the leaf nodes, which can further improve performance for certain use cases like range queries.\n\n### Hash Tables\n\n\n\nHash tables are used for hash indexes, which are based on a hash function.\n\nA hash table consists of an array of buckets, with each bucket containing the addresses for rows in the data.\n\nHash indexes employ a hash function to map keys to their corresponding bucket in the hash table, enabling constant-time lookup operations.\n\nHash indexes provide fast equality lookups, as the hash function determines the exact location of the data based on the key.\n\nHowever, hash indexes do not support range queries or sorting efficiently.\n\n### Bitmaps\n\n\n\nEach bit in the bitmap corresponds to a row, and the value of the bit indicates whether the key value exists in that row.\n\nBitmap indexes use a bitmap (a binary array) to represent the presence or absence of a specific key value in each row of a table.\n\nBitmap indexes are well-suited for columns with low cardinality (a small number of distinct values) and for performing complex queries involving multiple conditions.\n\nBitmap operations like AND, OR, and NOT are performed efficiently using bitwise operations, making bitmap indexes suitable for analytical queries involving multiple columns.\n\n---\n\n# **6. How to use Database Indexes Smartly?**\n\nTo get the most out of database indexes, consider these best practices:\n\n- **Identify Query Patterns**: Analyze the most frequent and critical queries executed against your database to determine which columns to index and which type of index to use.\n- **Index Frequently Used Columns**: Consider indexing columns that are frequently used in WHERE, JOIN, and ORDER BY clauses.\n- **Index Selective Columns:** Indexes are most effective on columns with a good spread of data values (high cardinality). Indexing a `gender` column might be less beneficial than one with a unique `customer_id`.\n- **Use Appropriate Index Types**: Choose the right index type for your data and queries.\n- **Consider Composite Indexes**: For queries involving multiple columns, consider creating composite indexes that encompass all relevant columns. This reduces the need for multiple single-column indexes and improves query performance.\n- **Monitor Index Performance**: Regularly monitor index performance, remove unused indexes and adjust your indexing strategy as the database workload evolves.\n- **Avoid Over-Indexing**: Avoid creating too many indexes, as this can lead to increased storage requirements and slower write performance. Indexes take up extra disk space since they're additional data structures that need to be stored alongside your tables. Every time you insert, update, or delete data in a table with an index, the index needs to update too. This can slightly slow down write operations.","pageType":"system-design"}

Indexing

Ashish Pratap Singh

Get Premium