Indexing

Question 1

What is the purpose of database indices?

Answer 1

To enable efficient query processing by avoiding full relation scans

Question 2

What are the two basic types of indices?

Answer 2

Ordered indices and Hash indices

Question 3

What are the key factors for evaluating index techniques?

Answer 3

Access type support, lookup time, insertion time, deletion time, and space overhead

Question 4

What is a clustering/primary index?

Answer 4

An index where the search key defines the sequential order of the file

Question 5

What is a secondary index?

Answer 5

An index whose search key specifies an order different from the sequential order of the file

Question 6

What is a dense index?

Answer 6

An index with entries for every search-key value in the file

Question 7

What is a sparse index?

Answer 7

An index with entries for only some search-key values, usable only when records are sorted by search key

Question 8

What is a multilevel index?

Answer 8

An index that creates a sparse outer index on the original (inner) index to improve search efficiency

Question 9

How does B+-tree handle duplicates?

Answer 9

By either storing multiple entries or using buckets to store pointers to all records with the same key

Question 10

What is the main advantage of B+-tree over static indexing?

Answer 10

Maintains efficiency despite insertions and deletions without requiring reorganization

Question 11

What are the key properties of B+-trees?

Answer 11

All paths from root to leaf are same length, nodes have between ⌈n/2⌉ and n children

Question 12

What is bulk loading in B+-trees?

Answer 12

Efficient technique to build index by sorting entries first, then building tree bottom-up

Question 13

What is the main limitation of hash indices?

Answer 13

They don’t support range queries effectively

Question 14

How does overflow chaining work in hash indices?

Answer 14

Records that hash to a full bucket are stored in overflow buckets linked to the original bucket

Question 15

What is an LSM tree?

Answer 15

Write-optimized index with multiple B+-trees starting from in-memory to on-disk structures

Question 16

What is the key idea of buffer trees?

Answer 16

Associate buffers with internal B+-tree nodes to reduce write operations

Question 17

What are bitmap indices used for?

Answer 17

Efficient querying on multiple keys using bit arrays for each possible value

Question 18

What is the main advantage of learned indices?

Answer 18

Can transform log(n) lookup cost to constant time by learning data distribution

Question 19

What is ALEX?

Answer 19

An updatable learned index that combines ML models with traditional indexing techniques

Question 20

How does ALEX handle dynamic workloads?

Answer 20

Uses Gapped Arrays for efficient insertions and Model-based Inserts for placement prediction

Question 21

Why is sorting important for indexing?

Answer 21

Enables efficient index creation and maintenance, especially for B+-trees

Question 22

What is the complexity difference between comparison-based and distribution-based sorting?

Answer 22

Comparison-based: O(N log N), Distribution-based: O(NW) where W is the number of digits

Question 23

What is prefix compression in B+-trees?

Answer 23

Technique to increase fanout by storing only distinguishing prefixes of search keys in nonleaf nodes

Question 24

What happens during B+-tree node splitting?

Answer 24

When a node becomes too full, it’s split into two nodes with ⌈n/2⌉ entries in each

Question 25

How does a B+-tree maintain balance?

Answer 25

Through splitting when nodes are too full and merging when too empty

Question 26

What is the cost of B+-tree operations?

Answer 26

Proportional to the height of the tree, which is log⌈n/2⌉(N)

Question 27

What's the difference between B-tree and B+-tree?

Answer 27

B-tree eliminates redundant storage of search keys but requires additional pointer fields

Question 28

How does an R-tree handle spatial data?

Answer 28

Uses rectangular bounding boxes to index spatial objects in a hierarchical structure

Question 29

What are the limitations of ALEX?

Answer 29

Cannot handle adversarial workloads, duplicate keys, or concurrent updates

Question 30

What is the k-d tree structure?

Answer 30

A spatial index that recursively partitions space along different dimensions

Question 31

How does bitmap index handle multiple keys?

Answer 31

Uses logical AND/OR operations between relevant bitmaps

Question 32

What is temporal data indexing?

Answer 32

Uses specialized indices or R-trees to handle time intervals in data

Question 33

Why use stepped-merge in LSM trees?

Answer 33

Reduces insert cost by allowing multiple trees per level but increases query cost

Question 34

How does recursive model index improve over naive ML approach?

Answer 34

Creates hierarchy of smaller models, each responsible for specific key ranges

Question 35

What is the purpose of Gapped Arrays in ALEX?

Answer 35

Provides space for future insertions without requiring frequent reorganizations

Question 36

How does counting sort work?

Answer 36

Builds histogram of data and uses it to place elements in final position

Question 37

What determines the choice between sparse and dense indices?

Answer 37

Trade-off between space overhead and lookup efficiency

Question 38

Why are secondary indices always dense?

Answer 38

Because records with intermediate search-key values could be anywhere in file

Question 39

How does flash storage affect indexing?

Answer 39

Requires special consideration for write operations due to page erasure costs

Question 40

What are the benefits of in-memory indexing?

Answer 40

Allows for smaller nodes that fit in cache lines for better performance

Question 41

How does quadtree differ from k-d tree?

Answer 41

Divides 2D space into four quadrants instead of one dimension at a time

Question 42

When should bitmap indices be used?

Answer 42

When attributes have low cardinality and multiple-key queries are common