What is Database Indexing - Types of Indexing - DBMS

indexing image



An index for a file system works in the same way as the catalogued in a library. A library will have its books catalogued in many different ways- by author, by subject, by title and so on. When we want to look for a book by an author, we will choose the author catalogue. The catalogue will have the information about the book and using the catalogue we can locate the book from among the thousands of books in the library. In real world database with millions of record, indexes like the book catalogue will be too large to be handled efficiently. So we will have to look for more sophisticated indexing techniques.

         Basically there are two types of indexes-ordered indexes and hashed indexes. An ordered index is based on a sorted ordering of the value. A hashed index is based on the values being uniformly distributed using a mathematical function called hash function. There are several techniques for implementing ordered indexing and hashing and each technique is the best suited for a particular database application.  Each technique should be first evaluated before choosing one. Evaluation should be based on the following factors:

The indexing has various attributes:-

  • Access Types: This refers to the type of access such as value based search, range access, etc.
  • Access Time: It refers to the time needed to find particular data element or set of elements.
  • Insertion Time: It refers to the time taken to find the appropriate space and insert a new data.
  • Deletion Time: Time taken to find an item and delete it as well as update the index structure.
  • Space Overhead: It refers to the additional space required by the index

  • Indexing is defined based on its indexing attributes. 

  • Primary Index:-

        • If the index is created on the basis of the primary key of the table, then it is known as primary indexing. These primary keys are unique to each record and contain 1:1 relation between the records.
        • As primary keys are stored in sorted order, the performance of the searching operation is quite efficient.
        • The primary index can be classified into two types: Dense index and Sparse index.

    • Secondary Index:-

    • The secondary Index in DBMS can be generated by a field which has a unique value for each record, and it should be a candidate key. It is also known as a non-clustering index.
      This two-level database indexing technique is used to reduce the mapping size of the first level. For the first level, a large range of numbers is selected because of this; the mapping size always remains small.

      Example of secondary Indexing:-

      Let's understand secondary indexing with a database index example:
      In a bank account database, data is stored sequentially by acc-no; you may want to find all accounts in of a specific branch of ABC bank.
      Here, you can have a secondary index in DBMS for every search-key. Index record is a record point to a bucket that contains pointers to all the records with their specific search-key value.

    • Clustering Index:-

      • A clustered index can be defined as an ordered data file. Sometimes the index is created on non-primary key columns which may not be unique for each record.
      • In this case, to identify the record faster, we will group two or more columns to get the unique value and create index out of them. This method is called a clustering index.
      • The records which have similar characteristics are grouped, and indexes are created for these group.

      Example: suppose a company contains several employees in each department. Suppose we use a clustering index, where all employees which belong to the same Dept_ID are considered within a single cluster, and index pointers point to the cluster as a whole. Here Dept_Id is a non-unique key.

  • Sequential File Organization or Ordered Index File:-

  • In this, the indices are based on a sorted ordering of the values. These are generally fast and a more traditional type of storing mechanism. These Ordered or Sequential file organization might store the data in a dense or sparse format:

    • Ordered Indexing is of two types −
        • Dense Index
        • Sparse Index
    • Dense index:-
          • The dense index contains an index record for every search key value in the data file. It makes searching faster.
          • In this, the number of records in the index table is same as the number of records in the main table.
          • It needs more space to store index record itself. The index records have the search key and a pointer to the actual record on the disk.
      • Sparse Index:-

        In sparse index, index records are not created for every search key. An index record here contains a search key and an actual pointer to the data on the disk. To search a record, we first proceed by index record and reach at the actual location of the data. If the data we are looking for is not where we directly reach by following the index, then the system starts sequential search until the desired data is found.

    • Multilevel Index:-

      • Index records comprise search-key values and data pointers. Multilevel index is stored on the disk along with the actual database files. As the size of the database grows, so does the size of the indices. There is an immense need to keep the index records in the main memory so as to speed up the search operations. If single-level index is used, then a large size index cannot be kept in memory which leads to multiple disk accesses.

    • B+ Tree:-

      • A B+ tree is a balanced binary search tree that follows a multi-level index format. The leaf nodes of a B+ tree denote actual data pointers. B+ tree ensures that all leaf nodes remain at the same height, thus balanced. Additionally, the leaf nodes are linked using a link list; therefore, a B+ tree can support random access as well as sequential access.

        Structure of B+ Tree:-

        Every leaf node is at equal distance from the root node. A B+ tree is of the order n where n is fixed for every B+ tree.

    • Internal node:-
        • An internal node of the B+ tree can contain at least n/2 record pointers except the root node.
        • At most, an internal node of the tree contains n pointers.

        Leaf node:-

        • The leaf node of the B+ tree can contain at least n/2 record pointers and n/2 key values.
        • At most, a leaf node contains n record pointer and n key values.
        • Every leaf node of the B+ tree contains one block pointer P to point to next leaf node.

        Searching a record in B+ Tree:-

        Suppose we have to search 55 in the below B+ tree structure. First, we will fetch for the intermediary node which will direct to the leaf node that can contain a record for 55.
        So, in the intermediary node, we will find a branch between 50 and 75 nodes. Then at the end, we will be redirected to the third leaf node. Here DBMS will perform a sequential search to find 55.

      •  :-

        Important pros/ advantage of Indexing are:

        • It helps you to reduce the total number of I/O operations needed to retrieve that data, so you don't need to access a row in the database from an index structure.
        • Offers Faster search and retrieval of data to users.
        • Indexing also helps you to reduce tablespace as you don't need to link to a row in a table, as there is no need to store the ROWID in the Index. Thus you will able to reduce the tablespace.
        • You can't sort data in the lead nodes as the value of the primary key classifies it.

        Disadvantages of Indexing:-

        Important drawbacks/cons of Indexing are:

        • To perform the indexing database management system, you need a primary key on the table with a unique value.
        • You can't perform any other indexes in Database on the Indexed data.
        • You are not allowed to partition an index-organized table.
        • SQL Indexing Decrease performance in INSERT, DELETE, and U-PDATE query.
      • *********************************************************************************************

        एसी ही नया टेक्नोलॉजी ,Programming Language , Coding , C Language, C++ and computer system से रिलेटेड जानकारियाँ पाने के लिए हमारे इस वेबसाइट www.contents4you.com को सब्सक्राइब कर दीजिए | जिससे हमारी आने वाली नई पोस्ट की सूचनाएं जल्दी प्राप्त होगी |

        अगर आपको Post पसंद आये  है तो अपने  friends और  social media पर share करे.