Have you ever wondered how a database retrieves data without scanning the full table so quickly from millions of records? Such a phenomenon can be exemplified by looking for an information location from the index of a book rather than sequentially scanning all the pages until the intended one is reached. Similarly, database indexing is what makes this possible in a database management system.
We will try to understand the effectiveness of indexing from the perspective of disks and blocks. A disk works as the persistent data storage in a DBMS, which is basically organized into blocks.
Consider that a single block is of size 1024 bytes. In addition, you have 960 data records to store, each having a size of 256 bytes. Then, each block stores 1024/256= 4 data records, and the total blocks needed for 960 records is= 960/4= 240 blocks, right?
Now, suppose you want the 960th record. So, you have to access all the blocks from 1 to 240 to get the data. This results in a significant number of expensive disk i/o operations, which can make your query slow. Just think what may happen to the performance overhead when you have a couple of million records, depending on your growing application demand.
This is where DB indexing comes into play.
Now, consider that you have used indexing on the ID column, which holds information in the ID and the respective address for data. Say, each record in the index table consumes 32 bytes. Then, each block will contain 1024/32=32 index entries, and for 960 data records, the total required blocks are= 960/32=30.
Therefore, in the worst case, you have to access 30 blocks for a data record of the ID (selected search key), then 1 block to reach the actual data, totaling 31 blocks. With just one-level indexing, you have reduced disk i/o to a very low amount, making your query faster. This can further be improved via multi-level indexing.
Here. I have considered that the blocks are sequentially accessed for keeping things simple. In reality, databases use something called B+ Trees, where keys are stored in sorted order, making data lookup have logarithmic complexity.
However, indexing does not magically do something like this. It has its own set of complexities and trade-offs that you have to consider, since a sequential scan may still be cheaper and effective when you have to get almost all the data records. Thus, depending on the application scenario, you have to decide whether you need to use indexing or not.
But, at a high level, it is now understandable how database indexing can make queries faster.
Top comments (0)