Database Indexing

The following is a B-tree of the index we have created. The leftmost path indicates the smallest entry and the rightmost path indicates the largest entry. All queries running will start from the top node and work downwards, if the target entry is smaller than the current node it will take the left path, otherwise it will take the right path. In this case the search starts with Joe, then Nick and ends at Zen.

Some of you may be aware of why the name in the B-tree is truncated. It was an attempt to increase efficiency where the B-tree would limit the number of characters that could be entered into an entry. The B-tree will do it on its own and doesn’t require column data to be delimited. In the example above the B-tree limits entries to 4 characters.

Now lets talk about Clustered Index.

A clustered index is a unique index per table that uses a primary key to organize the data in the table. Clustered index ensures that primary keys are stored in increasing order, which is also the order in which tables are stored in memory. Clustered index has characteristics such as:

• Created when the table is created.
• Use the primary key sorted in ascending order.

You can create clustered index (automatically) like this

    create table users (id INT PRIMARY KEY, name VARCHAR)

Once filled, the table will look like this:

users table

The “Users” table already created will have a clustered index automatically, set in the “id” column called “users_pkey”:

users_pkey clustered index

When we search for data in a table by “id”, the ascending order of the columns allows for optimal search. because the numbers are sorted the lookup can navigate a B-tree which allows the lookup to occur in logarithmic time.
However, to find “name” in the table, we must look at each entry because this column has no index. This is where non-clustered indexes come in handy.

Now lets talk about Non-Clustered Index.

The non-clustered index is sorted for a specific field, from the primary table holding a pointer back to the original table entry. The first example shown is an example of a non-clustered table:

They are used to increase query speed on tables by making columns easier to search. Sorry for the extra column, I don’t know how to remove it from my app drawer :(.
We can create multiple non-clustered indexes. in 2008, we can create up to 999 non-clustered indexes on SQL server and there is no limit on PostgreSQL.
Now you may be curious about when to use index and when not to use it. Ok let’s talk about it.

When to use Indexes

Indexing is meant to speed up database performance, so using indexing every time significantly improves your database performance. As your database gets bigger and bigger, the more likely you are to see the benefits of indexing.

If you are still confused, here I give some points when to use indexing::

1. add frequently used columns in where clause or in join condition.
2. column containing with a wide range such as flagging is_deleted, statusetc.
3. column containing many null values.
4. large tables and most queries display data less than 2–4% of the total data.

When not to use Indexes

When data is written to the database, the original table (clustered index) is updated first and then all indexes of that table are updated. each time a write is made to the database, the index cannot be used until it is updated. if the database keeps receiving writes then the index will never be usable.

Here I give some points where we don’t need to use indexing:

1. Small table.
2. Columns that are not often used as conditions in queries.
3. Most queries return more than 2–4% of the total data.
4. Frequently updated tables.

NOTE: The newest version of Postgres (that is currently in beta) will allow you to query the database while the indexes are being updated

Finally, Last but not least. Let’s test indexing performance!!

Here I will test indexing performance using PostgreSQL. To test if indexing will reduce query time, you can run a set of queries in your database, record the time it takes for those queries to complete, then start creating indexes and rerun your tests.

Here I have a database with a total data of 100k. I use a count estimate query so that the data calculation is faster.

estimate count row data

To do this, try using the EXPLAIN ANALYZE clause in PostgreSQL:

Where will this produce:

The results above show that the query takes 22,798 ms to find the data named “Andrea”.

Now let’s create an index to “name” column and run explain and analyze query again with this line:

     CREATE INDEX users_name_idx ON public.users ("name");
     EXPLAIN ANALYZE SELECT * FROM users WHERE name = 'Andrea';

And now our database will produce like this: