Storage and Indexing Flashcards
Each table is stored on disk in a ____ __ _____
file of records
A record is a memory area logically divided in _____
fields
What 3 things does a record display?
- 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)
What 4 operations of file of records support?
Insertion (of records)
Deletion (of records)
Modification (of records)
Scan (of records)
Files of records are organized in _____
pages
A page is a unit of information _____ ____ or ______ __ disk
read from, written to
This section focusses on how file of records can be organized as a _______ of pages
collection
The simplest file organization structure is a _____ file
heap
In a heap file, records are stored in ______ order across pages and are retrieved by ___
random, rid
We implements heap files with a ______ ____ of pages or ______ of pages
linked list, directory
Heap files implemented with linked lists keep 2 linked lists: one with _____ pages and another with _____ pages
free, full
What are 2 disadvantages of the heap file implemented with linked lists?
- Free list pages are of variable length.
2. Must scan several pages to insert a record
In a heap file implemented with a directory, each directory points to a ____ page
data
In a heap file implemented with a directory, what are 2 was free space can be managed?
- a bit per entry
2. count amount of free space per entry
A page is a ________ of slots
collection
The format of a page depends on the type of _______ and support for ____ operations
record, CRUD
In packed pages with fixed-length records, records are stored in the first _ slots
n
in unpacked pages with fixed-length records, a ____ _____ tells which slots are free for records
bit array
In pages with variable-length records, the page is filled with _______ that point to a record and stores the ____ of the record
pointers, size
Pages with variable length records are also called a _______ __ ______
directory of slots
In directory of slots, records can be moved without changing ___
rid
____ length records give direct access to fields, but are inefficiently stored
fixed
What are two formats for variable length records?
- Fields delimited by special symbol
- Array of fields offset
What is an index?
a data structure that organizes data records on a disk based on search key
A _____ ______ is a record stored in an index file
data entry
Indexs allow _______ retrieval of all data records satisfying a condition on the _____ ___
efficient, search key
What are 3 ways to store a data entry in an index with search key value k?
- A data entry k*
- (k, rid)
- (k, rid-list)
What are the 2 main indexing strategies?
- Hashing
- Trees
In tree-based indexing, fan-out is the average number of ________
children
In tree-based indexing, the number of disk I/O needed to find a record is…
length of path to a leaf + number of leaf pages with qualifying data entries
