12 Physical Representation: Indexing and Hashing

Question 1

What are access methods?

Answer 1

A group of programs that allow operations to be applied to a file

Question 2

What is the purpose of indexing mechanisms?

Answer 2

To speed up the access to desired data

Question 3

What is an index?

Answer 3

A data structure that allows us to locate information faster than with sequential scan

Question 4

What is a search key?

Answer 4

An attribute or set of attributes used to look up records in the file

Question 5

What does an index file contain?

Answer 5

Records called index entries in the form (SearchKey, Pointer)

Question 6

How do index entries compare in size to the original file?

Answer 6

They’re much smaller than the original file

Question 7

Give an example of a search key.

Answer 7

studentID

Question 8

What does a pointer indicate in an index entry?

Answer 8

Where to look in the original data file, e.g., ‘block 5, position 3’

Question 9

What are the two basic kinds of indices?

Answer 9

• Ordered indices
• Hash indices

Question 10

How are ordered indices structured?

Answer 10

Search keys sorted by search key value

Question 11

How are hash indices structured?

Answer 11

Search keys distributed uniformly across buckets using hash function

Question 12

What is a hash function?

Answer 12

A function always applied to the search key to determine bucket placement

Question 13

Provide an example of a hash function application.

Answer 13

hash(StudentID) = 105 % 3 = 0, so add record to bucket 0

Question 14

What determines the block a record will go in when using hash indices?

Answer 14

Bucket placement

Question 15

How is record position inside a block usually determined?

Answer 15

Based on sequential insertion (first inserted is first)

Question 16

What are the main evaluation metrics for an index?

Answer 16

Accuracy, efficiency, access time, insertion time, deletion time, space overhead.

These metrics help determine the effectiveness and performance of an indexing system.

Question 17

What is the tradeoff associated with indexing?

Answer 17

Faster access vs more storage used.

This tradeoff highlights the balance between speed of retrieval and the storage space required for the index.

Question 18

What is a primary index?

Answer 18

An index that specifies the sequential order of a file, typically using the primary key.

It is also known as a clustering index.

Question 19

What is an index-sequential file?

Answer 19

An ordered sequential file that has a primary index.

This type of file structure allows for efficient data retrieval.

Question 20

What is a secondary index?

Answer 20

An index used when data is not stored in a sequential order that matches the search key.

It is also referred to as a non-clustering index.

Question 21

How does a secondary index differ from a primary index?

Answer 21

A secondary index points to a bucket rather than directly to records.

This can lead to increased storage overhead.

Question 22

What is a dense index?

Answer 22

An index with one entry for every search key value in the file.

If a dense index has fewer entries than the original table, the search key cannot be the primary key.

Question 23

What is a sparse index?

Answer 23

An index that contains records for only some search key values.

Sparse indices are efficient in terms of space and maintenance.

Question 24

What is the advantage of using a sparse index?

Answer 24

Requires less space and less maintenance than dense indices.

However, it is generally slower for locating records.

Question 25

How do you locate a record with a search key value K using a sparse index?

Answer 25

Find the index record with the largest search key value < K. ## Footnote This method allows you to efficiently navigate to the desired record.

Question 26

What is the main difference between a dense index and a sparse index?

Answer 26

Dense index allows faster retrieval but requires more space and maintenance. Sparse index is slower in retrieval but requires less space and maintenance.

Question 27

What is a block in the context of a sparse index?

Answer 27

A block is a fixed unit of storage on disk that holds multiple records or index entries in a database system.

Question 28

What solution can be used if the primary index does not fit in memory?

Answer 28

Create a sparse index on the primary index itself to reduce the amount of data that needs to be loaded into memory.

Question 29

What is the outer index in the context of sparse indexing?

Answer 29

The outer index is a sparse index of the primary index.

Question 30

What is multilevel indexing?

Answer 30

Multilevel indexing is creating an outer index for the outer index if it is still too large.

Question 31

What must happen to indices at all levels during insertion or deletion?

Answer 31

Indices at all levels must be updated on insertion/deletion from the original file.

Question 32

What is the root node in a B+ tree?

Answer 32

The root node is the topmost node of the tree and serves as the starting point for all search operations.

Question 33

What are internal nodes in a B+ tree used for?

Answer 33

Internal nodes are used for indexing and routing search operations to the correct leaf node.

Question 34

What do leaf nodes in a B+ tree contain?

Answer 34

Leaf nodes contain actual data records or pointers to data records.

Question 35

What is a limitation of indexed-sequential files?

Answer 35

Performance degrades as the file grows due to overflow blocks, requiring periodic reorganization.

Question 36

What is an advantage of B+ Trees over indexed-sequential files?

Answer 36

B+ Trees provide automatic reorganization and performance maintenance.

Question 37

How does a B+ tree maintain efficiency as the file grows?

Answer 37

It is a self-balancing tree structure that automatically reorganizes itself with each insertion and deletion.

Question 38

Where is data inserted in a B+ tree?

Answer 38

Data is inserted at leaf nodes.

Question 39

What is a minor disadvantage of B+ trees?

Answer 39

The restructuring of the tree requires some extra overhead as nodes are split or merged.

Question 40

What extra space is required in B+ trees?

Answer 40

Extra space is required because each internal node points to child nodes and each leaf node holds pointers to actual data records.

Question 41

What properties does a B+ Tree satisfy?

Answer 41

1. All paths from root to leaf are of the same length. 2. Each non-root, non-leaf node has between [n/2] and n children. 3. A leaf node has between [(n-1)/2] and n-1 values.

Question 42

What is the maximum branching factor in a B+ Tree?

Answer 42

n, which is the maximum number of children a node can have.

Question 43

How can databases use indexes for a query with multiple conditions?

Answer 43

1. Use index on the first condition to filter records, then apply the second condition. 2. Find pointers for both conditions and intersect the results.

Question 44

What does a composite search key mean?

Answer 44

An index built on more than one column, for example, (branch_name, balance).

Question 45

When is an index on multiple attributes efficient?

Answer 45

1. When the query involves exact values for all indexed columns. 2. When it involves an exact value for the first column and a range for the following column.

Question 46

When is an index on multiple attributes inefficient?

Answer 46

When the query involves a range for the first column and an exact value for the following column.

Question 47

What is static hashing?

Answer 47

A method to quickly find data in a file using a hash function.

Question 48

What is a bucket in static hashing?

Answer 48

A unit of storage containing one or more records, typically a disc block.

Question 49

What is the purpose of a hash function in static hashing?

Answer 49

To convert a search key into a bucket address, allowing direct access to the corresponding bucket.

Question 50

What is the cost of periodic reorganization in ordered indexing and hashing?

Answer 50

It depends on how often data is inserted or deleted, as both methods require reorganization.

Question 51

When should hashing be preferred over ordered indexing?

Answer 51

For fast average performance and when searching by exact key.

Question 52

When is ordered indexing better than hashing?

Answer 52

For predictable worst-case time performance and for range queries.

Question 53

What does PostgreSQL support regarding hash indices?

Answer 53

PostgreSQL supports hash indices but discourages their use due to poor performance.

Question 54

How can you create an index in SQL?

Answer 54

Using the command: CREATE INDEX index_name ON relation_name (attribute_list).

Question 55

What is the difference between hash organization and hash index?

Answer 55

Hash organization stores records directly in a file using hashing, while hash index maps search keys to the location of records stored elsewhere.

Question 56

What does the command CREATE UNIQUE INDEX specify?

Answer 56

It specifies that the search key is a candidate key.

Question 57

How do you drop an index in SQL?

Answer 57

Using the command: DROP INDEX index_name.