Database indexing - how does it work?

Question

how does indexing increases the performance of data retrieval?

How indexing works?

Answer 1

Database products (RDMS) such as Oracle, MySQL builds their own indexing system, they give some control to the database administrators however nobody exactly knows what happens on the background except people makes research in that area, so why indexing :

Put simply, database indexes help speed up retrieval of data. The other great benefit of indexes is that your server doesn't have to work as hard to get the data. They are much the same as book indexes, providing the database with quick jump points on where to find the full reference (or to find the database row).

There are many indexing techiques for example :

• Primary indexing, secondary indexing
• B-trees and variants (B+-trees,B*-trees)
• Hashing and variants (linear hashing, spiral etc.)

for example, just think that you have a database with the primary keys are sorted (simply) and these all data is stored in blocks (in hdd) so everytime you want to access the data you don't want to increase the access time (sometimes called transaction time or i/o time) the indexing helps you which data is stored in which block by using these primary keys. Alice (primary key is names, not good example but just give an idea)

Alice
...
...
AZ...
Bob
Bri
...
Bza
...

Now you have an index in this index you only store Alice and Bob and the blocks they point, with this way users can access the data faster.The RDMS deals with the details.

I don't give the details but if you want to delve these topics, i offer you take an Database course or look at this popular book which is taught most of the universities.

Database Management Systems Ramakrishn CGherke

Answer 2

Each index keep the indexed fields stored separately, sorted (typically) and in a data structure which makes finding the right entries particularly easy. The database finds the entries in the index then cross-references them to the entries in the tables (Except in the case of clustered indexes and covering indexes, in which case the index has it all already). This cross-referencing takes time but is faster (you hope) than scanning the entire table.

A clustered index is where the rows themselves with all columns* are stored together with the index. Scanning clustered indexes is better than scanning non-clustered non-covering indexes because fewer lookups are required.

A covering index is where the query only requires columns which are part of the index, so the rest of the row does not need to be looked up (This is often good for performance).

* typically excluding blob / long text columns etc

Answer 3

How does an index in a book increase the ease with which you find the right page?

Much easier to look through an alphabetic list and then go to the right page than read every page.