Indexing is a term used in DBMS which is used to reduce the number of operations or lookups to find a record in a database.
Before, we dive right into the concept of indexing lets first understand why we needed it in the first place?
To understand Indexing we need to understand first the disk structure and how the data is stored in the disk.
A disk is divided into sectors ,tracks and blocks .
Each sector consist of multiple tracks->Intersection of tracks and sectors is called blocks ->Each byte of the block is called offset.
To locate a block address we need track id and sector id.
Block address = (sector id, track id)
Typically for study purpose we assume size of block as 512 bytes
To reach particular byte we need -> track id, sector id, block id
By spinning the disk the sectors are changed and by moving the disk tracks are changed
• Typically the entire database is stored on disk.
• Data must be moved from disk to main memory in order for the data to be operated on.
• After operations are performed, data must be copied back to disk if any changes were made.
• Disk storage is called direct access storage as it is possible to read data on the disk in any order (unlike sequential access).
• Disk storage usually survives power failures and system crashes.
Organizing the data on the main memory is done by Data Structures whereas , organizing the data on the disk efficiently so it can be utilized is done by DBMS.
Tables are stored on the hard disk of the database server. The database tables are usually divided into column and rows, just like a regular graphic table.
In a database table, the columns specify the information category and the data type and the rows hold the actual information.
How data is stored in disk
For eg :
Consider a tables with n columns with 100 records
Total size of each row in the table is 128 bytes
If the block size is 512 bytes then,
No of records per block = 512/128 = 4
Means we can store 4 rows in 1 block and next 4 in next block and so on
100 records = 100/4 = 25
25 blocks for 100 records
The time to search a record in a table depends upon the number of blocks.
As the number of records increases so will the number of blocks so to access an block with less time we use Indexing
We will see Indexing in Next blog post!