How to implement secondary indexes in databases?

TL;DR

A secondary index is used when queries do not align with the primary key. It is built on non primary or non key fields to speed up lookups when data is unordered. It remains dense and enables faster searches through an intermediate layer of pointers.

Transcript

Hello friends, welcome to Gate Smashers, today's topic is secondary index Secondary index is important from point of view UGC-Net and GATE Biggest problem here is that all material available online even offline also in books Secondary index topic is not 100% clear from there So in this video I'm starting from very basic level So that you can clear... Read More

Key Insights

• Secondary index is used when data is unordered or when queries target non primary fields.
• The primary index is sparse and built on the unique key such as employee ID, guiding most lookups.
• Secondary index can be dense, ensuring each record has an index entry, enabling direct access to records.
• When data is ordered around a unique key, primary index suffices, but non key queries require secondary indexing.
• A dense secondary index places a pointer for every record, ensuring complete coverage.
• A sparse index reduces entries by grouping multiple records under a single key, which can complicate lookups.
• Binary search can be used on ordered but unordered indexed data to improve performance.
• An intermediate layer may be needed for complex cases where a single index must map to multiple blocks or pointers.
• More videos from this channel:
  • How to use a clustered index in a database
  • How to hash data and use a hash table efficiently
  • What is the difference between delete drop and truncate in SQL
• More from this channel: Gate Smashers

Questions & Answers

Q: How does a secondary index improve search performance for non key queries?

A secondary index improves search performance for non key queries by providing an alternative access path to the data that is not based on the primary key. It creates an index on attributes such as name or PAN that are not the primary key, enabling the system to locate the relevant data quickly via pointers rather than scanning the entire table. This can substantially reduce lookup times when queries depend on non key attributes and data is unordered.

Q: What is the difference between dense and sparse indexing in the context of secondary indexes?

Dense indexing means every record in the data set has an entry in the index, so a direct pointer to each record can be found. Sparse indexing involves fewer index entries, often grouping multiple records under a single index key, which can save space but may require additional lookups. In secondary indexes, dense indexing is typically used to ensure faster access, while sparse methods may appear in intermediate layers when data is highly non uniform.

Q: Why is a secondary index described as dense in this video?

The video describes a secondary index as dense because each record in the dataset has a corresponding index entry in the secondary index. This ensures that when you search by the secondary key, there is a direct mapping to the records without skipping entries. This characteristic is emphasized to explain why the index remains effective for quick data retrieval.

Q: When would you use a secondary index instead of relying only on a primary key?

You would use a secondary index when queries are conducted on attributes other than the primary key, such as a name or a PAN number. If the data is unordered and most searches are not based on the primary key, a secondary index provides a faster lookup path by creating a separate index table on the non key column. This helps maintain performance for diverse query patterns.

Q: How is time complexity described for traversing a secondary index?

Time complexity for traversing a secondary index is described as logarithmic with respect to the number of blocks in the index, written as log N. If there is an additional intermediate layer, the total lookup may involve multiple logarithmic steps plus contributions from multiple pointers, but the overall behavior remains dominated by logarithmic searches through the index structure.

Q: What role does an intermediate layer play in a multi pointer secondary index?

An intermediate layer in a multi pointer secondary index handles cases where a single index key can map to multiple data blocks. This layer stores blocks of record pointers for each key, allowing the index to direct the search to the correct subset of blocks. It adds a level of indirection that enables handling non unique keys efficiently.

Q: What are the two base scenarios for applying a secondary index as explained in the video?

The two base scenarios are when the data is unordered and the secondary key is a unique value, and when the data is unordered and non key values are used. In the first case, the index can be built on a unique key like PAN, supporting fast lookups. In the second case, for non unique fields like names, an intermediate layer is required to manage multiple records tied to the same key.

Q: How does the video describe the relationship between primary and secondary indexes in terms of data layout?

The video explains that primary indexes are built on the unique primary key and organize data in a sorted fashion, which makes lookups efficient for that key. Secondary indexes provide alternate access paths when queries target other attributes. They complement the primary index by enabling quick searches on non key fields, with dense indexing ensuring coverage of all records for those attributes.

Summary & Key Takeaways

• Secondary index concepts are introduced from the basics, explaining when and why to use it

• The video distinguishes primary, clusterred, and secondary indexes and their tradeoffs

• It demonstrates dense versus sparse indexing and how pointers are used to locate data efficiently