Database Storage (3 Part Series)
The usual index and pointer to the record structure of indexing is not beneficially in all the cases different indexing techniques are used to help combat different records present in databases.
Below are few different types of Indexing.
Primary Index - In primary index, there is a one-to-one relationship between the entries in the index table and the records in the main table.
Dense primary index
• The number of entries in the index table is the same as the number of entries in the main table.
• Each and every record in the main table has an entry in the index.
• For large tables,to locate a record we find the index record with the largest search key. Value less than or equal to the search key value.
• We start at that record pointed to by the index record, and proceed along the pointers in the file (that is, sequentially) until we find the desired record.
• It may happen sometimes that we are asked to create an index on a non-unique key, such as Dept-id.
• There could be several employees in each department.
Here we use a clustering index, where all employees belonging to the same Dept-id are considered to be within a single cluster, and the index pointers point to the cluster as a whole.
Multilevel Index/Secondary Index:
• A multilevel index considers the index file, which we will now refer to as the first (or base) level of a multilevel index, as an ordered file with a distinct value for each K(i).
• In this case, the original index file is called the first-level index and the index to the index is called the second-level index.
• We can repeat the process, creating a third, fourth ... top level until all entries of the top level fit in one dis
When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time. The main idea of using B-Trees is to reduce the number of disk accesses.
We will see use of B and B+ trees in next blog post!