Database Indexing

What is the core purpose of database indexes?

To optimize data search and access efficiency

What are the limitations of sequential scan

High worst-case complexity, time-consuming for large datasets, and inefficient for complex predicates

What components make up an index structure?

Key-pointer pairs that reference block/page, record offset, or full record

Key contains a field value for which an index is created

Pointer is a reference to anchoring block/record or tuple itself

Why can only one primary index exist per file?

Because data can only be physically ordered in one way within a file

Sparse index, entry per block

How do hash-based indexes perform with point queries?

They provide the fastest performance for exact match queries

O(1)

What are the three essential properties of hash functions?

Deterministic, computationally fast, and uniform mapping

What makes B+ Trees efficient for range queries?

Sibling leaf node linking and values stored only in leaf nodes

it is always balanced

and is well-suited for any dynamic updates

What is the time complexity of B-Tree operations?

O(log n) for all operations

How do you calculate records per block?

Divide block size by record size (Example: 4096/100 ≈ 40 records)

What are key considerations when creating indexes?

Order-preserving capabilities, balanced structure, reusability, and adaptability to updates

What database tuning techniques improve performance?

Collecting query statistics, identifying expensive queries, and creating secondary indexes on join attributes

What advantages do B+ Trees have over regular B-Trees?

Support for duplicate keys and more efficient range queries

What makes an index "lightweight"?

Minimal storage requirements while enabling high-speed searching

How does binary search improve block scanning?

Reduces the number of blocks needed to scan logarithmically

What are sparse index properties?

Contains entries equal to number of data blocks, not total records

What types of queries can indexes enable?

Point queries and range queries

What should be considered when selecting an index type?

Query patterns, data characteristics, and performance requirements

How do secondary indexes differ from primary indexes?

Can have multiple secondary indexes per file and don't determine physical data ordering

What is the space complexity of hash-based indexes?

O(n) where n is the number of records

What makes B-Trees self-balancing?

Automatic redistribution of nodes to maintain balance during insertions and deletions

When is the indexing field a nonkey?

When a clustering index is used, then as a secondary index. No block anchoring is used. The index types can be dense or nondense

What is extendible hashing?

It allows the hash table to grow or shrink dynamically as the dataset changes

Linear hashing?

Common dynamic hash table used to deal with unbalacend/skew key distributions

it decouples overflows and bucket splits

uses muliple hash functions

a overflow can only trigger a split where the pointer is.