A database index is a data structure that improves the speed of data retrieval operations on a database table. It works in a similar way to an index in a book: instead of scanning the entire book to find a particular topic, you can go to the index, find the topic, and then go directly to the pages that contain this topic.
Let’s assume a phone book with thousands of names and phone numbers. If you were tasked to find the phone number of a particular person, the brute force method would be to start from the first page and flip through each subsequent page until you find the person. However, if the phone book has an index, you can directly go to the page where the person’s details are recorded, thus saving a lot of time.
In databases, indices work similarly. Suppose we have a ‘Customers‘ table in a database and we regularly need to find customers based on their ‘CustomerID‘. Without an index on ‘CustomerID‘, the database engine would need to look at each row in the Customers table to find a particular ‘CustomerID‘ (this is known as a full table scan), which can be very slow if there are many customers. However, with an index on ‘CustomerID‘, the database engine can quickly find the row for a particular ‘CustomerID‘ without needing to look at every row.
Indices can also be made on multiple columns, known as composite index. For example, if an application often needs to look up customers by ‘LastName‘ and ‘FirstName‘ together, then a composite index on (‘LastName‘, ‘FirstName‘) would speed up these lookups.
However, there’s a trade-off while using indexing. While it speeds up data retrieval, it slows down data insertion, update, and deletion. This is because every time data is changed, the index also needs to be updated.
Generally speaking, the database engine uses a B-tree data structure for indexes. A B-tree keeps data sorted and allows searches, insertions, and deletions in logarithmic time.
The diagram of a simple B-tree index on ‘CustomerID‘ might look something like this:
15
/ \
10 20Here, each node represents a page on disk where a certain range of ‘CustomerIDs‘ are stored. The root node says that ‘CustomerIDs‘ less than 15 are on the left and ‘CustomerIDs‘ greater than or equal to 15 are on the right. Then each subsequent node tells you which disk page to look at, until you arrive at the leaf node that holds the ‘CustomerID‘.
So, creating the appropriate indices can greatly speed up data retrieval, but they should be used judiciously, considering the nature of operations performed on the database and the size of the tables.