Indexing & Trees

File Structures & Indexing

Indexing is used to optimize the retrieval of data from a database.

• Primary Index: A primary index is an ordered file, records of fixed length with two fields. First field is the same as the primary key as a data file and the second field is a pointer to the data block, where the key is available. The average number of block accesses using index = log2Bi + 1, where Bi = number of index blocks.
• Clustering Index: Clustering index is created on data file whose records are physically ordered on a non-key field (called Clustering field).
• Secondary Index: Secondary index provides secondary means of accessing a file for which primary access already exists.

B Trees & B+ Trees

Tree-based indexing structures are widely used in databases.

• B Trees: At every level, we have Key and Data Pointer and data pointer points to either block or record. Root of B-tree can have children between 2 and P, where P is Order of tree. Internal node can have children between ⌈ P/2 ⌉ and P. Internal node can have keys between ⌈ P/2 ⌉ – 1 and P-1.
• B+ Trees: In B+ trees, the structure of leaf and non-leaf are different. Order of non-leaf will be higher as compared to leaf nodes. Searching time will be less in B+ trees, since it doesn’t have record pointers in non-leaf because of which depth will decrease.