We know that data in the form of records is stored. There is a main field in any record, which allows it to be recognized uniquely.
Indexing is a data structure technique based on certain attributes on which the indexing has been performed to efficiently extract information from database files. In database systems, indexing is close to what we see in books.
Based on its indexing attributes, indexing is specified. Indexing can be of the types below-
Ordered Indexing is of two types −
In the dense index, for every key search value in the database, there is an index record. This makes searching quicker, but requires more space for index records to be stored on their own. Index records contain the value of the search key and a pointer to an actual disk record.
Index records are not generated for each search key in the Sparse Index. There is a search key and an actual pointer to the data on the disk in an index record here. We first proceed to an index record to search for a record and reach the actual location of the data. If the data we are looking for is not where we reach directly by following the index, then before the desired data is found, the system starts sequential searching.
Search-key values and data pointers comprise the index records. The multilevel index, along with the individual database files, is stored on the disk. As the database's size increases, so does the indices' size. In order to speed up the search operations, there is an immense need to retain the index records in the main memory. If a single-level index is used, it is difficult to hold a broad index in memory, which leads to multiple accesses to the disk.
In order to make the outermost level so small that it can be stored in a single disc block, which can easily be accommodated anywhere in the main memory, the multi-level index helps break down the index into many smaller indices.
A B+ tree follows a multi-level index format and is a balanced binary search tree. A B+ tree's leaf nodes denote actual data pointers. The B+ tree ensures that all leaf nodes stay balanced at the same height. In addition, a link list connects the leaf nodes; a B+ tree can therefore allow both random access and sequential access.
Structure of B+ Tree
Each node on the leaf is the same distance from the root node. For any B+ tree, a B+ tree is of the order n where n is fixed.
Internal nodes −
Leaf nodes −
B+ Tree Insertion
B+ Tree Deletion