How Database Indexes make Read faster

We go over how indexes help a database run faster. While we're at it, we'll go over how data is read from disc, how indexes are built, serialised, and saved on disc, and how data is swiftly read using the proper set of indexes.

An index is a data structure that aids a database in quickly finding data. It is a distinct table that has a copy of one or more columns from the main table, as well as a pointer to the row in the main table that contains that data.

When you make a query, the database first checks to determine if the column(s) you are querying have an index. If there is, the database searches the index for rows that match your query before retrieving the data from the main table. This is far faster than searching the entire primary table for the data.

Let's understand first like- How data is getting stored on disc...?

the most common ways that tables are stored on disk:

Heap files: In a heap file, the rows are stored in no particular order. This is the simplest way to store a table, but it can make it difficult to find specific rows.
B-tree files: In a B-tree file, the rows are stored in a sorted order. This makes it much faster to find specific rows, but it takes up more space on disk.
Hash files: In a hash file, the rows are stored in a hash table. This is a very fast way to find specific rows, but it can be difficult to insert or delete rows from a hash file.

Let's start from zero and think how database stores the data..?

To answer this- Any database that wishes to store its records on disc must first seralize and store them. But the crucial point is how this serilization occurs.

To understand this let's take an example if relational database table named "customer" that has certain columns like.

Only in a hypothetical case Customer table contains 5 columns, a record reach of 200B, and 1000 records.

total size of table = 200B * 1000 = 200000B.

Now, how does the disc read work ?

one disk read = one block read 600B(*)

In this case, even if we just require one byte, it will read the full 600B block that includes that byte.

Consider our client table as a series of blocks.

The complete "customer" with 1000 rows fits within 1000/3=33.3 ~ 34 blocks.

As a result, reading the full table will necessitate the database engine accessing 34 blocks from disc.

In a hypothetical scenario Reading one block takes one second, and reading the full table takes 34 seconds. Consider this: we need to discover clients with the pin 005. What the flow will look like.

Iterate through the table row by row (block by block).
Read the memory block.
Check each record for Pin == 005.
If yes, insert the record into the output buffer.
If no, throw away
As a result, the output buffer is returned.

The time required to answer this query is the same as the time required to read the block 34 blocks= 43 seconds.

Let's explore how Indexes speed up this flow.

Indexes:- This is a smaller referential table that stores new references against the value of the indexes.

i.e.- create an referential table based on PIN column.

Because the index table will have 1000 entries, the overall size of the index table will be 16 * 1000 = 16000B.

One disk block = 600

So Index table will need 27 blocks almost.

Now, after building Index, the previous flow will be like

Read the index and take note of any Ids that match the criteria.
Retrieve the actual records from the disc for the relevant Ids.

Now hashtag#blocks read= 27 in worst case.

Relevant Id with Pin== 005 are [7]

so, there is one record present with id 7 is present in block 3

so total block read will be 27 +1 =28 = 28 sec

Blocks read before creating Index= 1000

Blocks read after creating Index= 28

gain is almost 10 times.

Think about this gain on the scale

Bonus 😉

Here are some tips for creating indexes:

Create indexes on columns that are frequently used in queries.
Create indexes on columns that are used in joins.
Create indexes on columns that are used in sorting.
Do not create indexes on columns that are frequently updated.
Keep indexes up to date. 💡