Storage and Indexing

Question 1

Each table is stored on disk in a ____ __ _____

Answer 1

file of records

Question 2

A record is a memory area logically divided in _____

Answer 2

fields

Question 3

What 3 things does a record display?

Answer 3

• Corresponds to a row of values in the table
• Each has the same number of fields (but maybe not the same length)
• Each has a unique identifer (rid)

Question 4

What 4 operations of file of records support?

Answer 4

Insertion (of records)
Deletion (of records)
Modification (of records)
Scan (of records)

Question 5

Files of records are organized in _____

Answer 5

pages

Question 6

A page is a unit of information _____ ____ or ______ __ disk

Answer 6

read from, written to

Question 7

This section focusses on how file of records can be organized as a _______ of pages

Answer 7

collection

Question 8

The simplest file organization structure is a _____ file

Answer 8

heap

Question 9

In a heap file, records are stored in ______ order across pages and are retrieved by ___

Answer 9

random, rid

Question 10

We implements heap files with a ______ ____ of pages or ______ of pages

Answer 10

linked list, directory

Question 11

Heap files implemented with linked lists keep 2 linked lists: one with _____ pages and another with _____ pages

Answer 11

free, full

Question 12

What are 2 disadvantages of the heap file implemented with linked lists?

Answer 12

1. Free list pages are of variable length.

2. Must scan several pages to insert a record

Question 13

In a heap file implemented with a directory, each directory points to a ____ page

Answer 13

data

Question 14

In a heap file implemented with a directory, what are 2 was free space can be managed?

Answer 14

1. a bit per entry

2. count amount of free space per entry

Question 15

A page is a ________ of slots

Answer 15

collection

Question 16

The format of a page depends on the type of _______ and support for ____ operations

Answer 16

record, CRUD

Question 17

In packed pages with fixed-length records, records are stored in the first _ slots

Answer 17

n

Question 18

in unpacked pages with fixed-length records, a ____ _____ tells which slots are free for records

Answer 18

bit array

Question 19

In pages with variable-length records, the page is filled with _______ that point to a record and stores the ____ of the record

Answer 19

pointers, size

Question 20

Pages with variable length records are also called a _______ __ ______

Answer 20

directory of slots

Question 21

In directory of slots, records can be moved without changing ___

Answer 21

rid

Question 22

____ length records give direct access to fields, but are inefficiently stored

Answer 22

fixed

Question 23

What are two formats for variable length records?

Answer 23

• Fields delimited by special symbol

- Array of fields offset

Question 24

What is an index?

Answer 24

a data structure that organizes data records on a disk based on search key

Question 25

A _____ ______ is a record stored in an index file

Answer 25

data entry

Question 26

Indexs allow _______ retrieval of all data records satisfying a condition on the _____ ___

Answer 26

efficient, search key

Question 27

What are 3 ways to store a data entry in an index with search key value k?

Answer 27

1. A data entry k*
2. (k, rid)
3. (k, rid-list)

Question 28

What are the 2 main indexing strategies?

Answer 28

• Hashing

- Trees

Question 29

In tree-based indexing, fan-out is the average number of ________

Answer 29

children

Question 30

In tree-based indexing, the number of disk I/O needed to find a record is…

Answer 30

length of path to a leaf + number of leaf pages with qualifying data entries