The current chapter covered the fundamentals of indexing. The chapter built on the fundamentals of linear indexing, and extended it to ISAM. The linear indexing method is a good approach for static datasets which do not change over time; however, if any updates are required, they come at a very high computation cost. To address this issue, the ISAM indexing approach has been introduced, which tries to address the updating issue of databases. But it is still suitable for a few updates only.

The chapter also covered tree-based indexing structures which utilize the binary search tree-based structure to minimize search and updates. Multiple tree-based indexing approaches were also covered. The most primitive version is a 2-3 tree which uses the two-key and three-child strategy. The 2-3 tree indexing approach is a good starting point for tree-based indexing approaches, but retrieval of data from disk-based storage is slow.

The approach is further generalized as a B-tree which ensures that the tree is balanced, and is a suitable indexing structure for disk storage as well. The B+ tree, an enhanced version of B-tree which stores data only in the leaf (B+ tree) is discussed in later part of the chapter. The B+ tree stores data only in leaves, and all leaves are interconnected, which allows multiple types of aggregation queries to be efficiently executed. The next chapter will introduce graph-based data structures, which are highly useful in understanding relationships between objects.