1Why is sorting important in databases?
to support order by queries grouping duplicate elimination joins and indexing
2What is the main challenge of sorting in DBMS?
data is much larger than main memory
3What dominates cost in external sorting?
disk io cost
4What is the goal when designing external sorting algorithms?
reduce i o operations
5What is the time complexity of merging two sorted lists?
o_n plus m
6How does merge work?
compare elements from two lists and move the smaller one forward
7What must be true about lists before merging?
they must already be sorted
8What is external merge sort used for?
sorting data larger than memory using disk
9What are the two phases of two way external sort?
prepare and merge
10What happens in pass 0 of external sort?
read a page sort it and write it back
11How many buffers are needed for two way merge?
three buffers
12What is a run in external sorting?
a sorted sublist of pages
13What happens in each merge pass?
merge smaller runs into larger sorted runs
14What is the cost of one pass in external sort?
2n i/o operations
15What is total i o cost in two way merge sort?
2n times number of passes
16How many passes in two way merge sort?
log base 2 of n plus 1
17What is the idea behind m way merge sort?
use more buffers to merge more runs at once
18What happens in phase 0 of m way merge?
sort m pages at once into one run
19How many runs are produced in pass 0?
n divided by m
20How many buffers are used in merging?
m minus 1 for input and 1 for output
21What is the benefit of using more buffers?
fewer passes and lower i o cost
22What is the formula for number of passes in m way sort?
1 plus log base m minus 1 of n over m
23What is total i o cost in m way sort?
2n times number of passes
24What is a table scan?
reading every page and record in a table
25What is the i o cost of table scan?
n page reads
26What is the minimum memory needed for table scan?
one block
27Why are table scans inefficient?
they read all data even if few records match
28What is an index used for?
to speed up access to data
29What is a search key?
attribute used to look up records
30What does an index entry contain?
search key value and pointer
31Why are index files smaller than data files?
they store only keys and pointers
32What are types of indexes?
dense sparse primary secondary multi level
33What is a dense index?
one index entry per record
34What is a sparse index?
one index entry per data block
35Can sparse index be used on unordered files?
no
36Can dense index be used on unordered files?
yes
37What is a primary index?
index on the sorted ordering column
38What is a secondary index?
index on a non ordering column
39What type of index must secondary index be?
dense
40What is an advantage of sparse index?
uses less space
41What is an advantage of dense index?
can determine if record does not exist without data file
42What is a drawback of dense index?
requires more space and updates
43What is a multi level index?
index built on top of another index
44Are higher level indexes dense or sparse?
sparse
45Why use multi level indexes?
reduce search time further
46What is index binary search?
search sorted index by checking middle entries
47How does sparse index locate a key?
find closest smaller key then scan data block
48What happens when deleting in dense index?
may require updating many index entries
49What happens when deleting in sparse index?
less reorganization needed
50Why keep free space in blocks?
to allow easier insertions
51What are overflow blocks?
extra blocks used when insertion space is full
52What is a benefit of primary index?
records with similar keys are stored together enabling sequential io