Indexing (B+ Trees)
Note: the pictures are slightly simplified, do no show any record pointer for the leaf
nodes. For drawing B+ trees you could use tools such as the following:
1. Assume we have the following B+-tree of order 1. Each node in the index must
have either 1 or 2 keys (i.e, 2 or 3 pointers), and the leaves can hold up to 2 entries.
a) What is the maximum number of insertions we can perform without changing the
height of this tree? Illustrate it by giving such an insertion pattern.
b) What is the minimum number of keys we can insert in order to trigger a change in
the height of this tree? Illustrate it by giving such an insertion pattern.
2. Suppose we have an Alternative 2 unclustered index on the attribute pair
(assignment_id, student_id) with a depth of 3 (one must traverse 3 index pages to
reach a leaf page).
Here is the schema:
CREATE TABLE Submissions (
record_id integer UNIQUE,
assignment_id integer,
student_id integer,
time_submitted integer,
grade_received byte,
comment text,
regrade_request text,
PRIMARY KEY(assignment_id, student_id) );
CREATE INDEX SubmissionLookupIndex ON Submissions (assignment_id,
student_id);
Assume the table and its associated data takes up 12 MB on disk and that page size
is 64 KB.
(This excludes the index pages, but includes extra space allocated for future
insertions, therefore pages are assumed 2/3 full).
Assume also you know the size of each attribute type: integer 4B, text: 32B, byte: 1B.
Page pointers (page Ids) are 2B long, row Ids are 4B long.
a) How many records do we have in the Submissions table ?
b) We want to scan all the records in Submissions. How many I/Os will this operation
take ?
c) The following instruction is executed:
UPDATE Students
SET grade_received=85
WHERE assignment_id=20 AND student_id=12345;
How many I/Os will this operation take?
d) In the worst case, how many I/Os does it take to perform an equality search on
attribute grade_received?
3. Consider the B+ tree index of order d = 2 shown below.
a) Show the index resulting from inserting a data entry with key 9 into this index.
b) Show the index resulting from inserting a data entry with key 3 into the original
index. How
many page reads and page writes are necessary for this insertion?
c) Show the index resulting from deleting the data entry with key 8 from the original
index,
assuming that the left sibling is checked for possible redistribution.
d) Show the index resulting from deleting the data entry with key 8 from the original
index,
assuming that the right sibling is checked for possible redistribution.
e) Show the index resulting from starting with the original index, inserting a data entry
with key
46 and then deleting the data entry with key 52.
f) Show the index resulting from deleting the data entry with key 91 from the original
index.
4. Relational Algebra. Consider the following schema:
Suppliers(sid: integer , sname: string , address: string )
Parts(pid: integer , pname: string , color: string )
Catalog(sid: integer , pid: integer , cost: real )
The key fields are underlined, and the domain of each field is listed after the field
name. Therefore sid is the key for Suppliers, pid is the key for Parts, and sid and pid
together form the key for Catalog. The Catalog relation lists the prices charged for
parts by Suppliers.
Describe in plain English (without using words such as join, project, select, etc) what
the following RA queries compute (if they compute something):
a) πsname (πsid ((σcolor=redParts) ⨝ (σcost<100Catalog ))⨝Suppliers)
b) πsname (πsid ((σcolor=redParts) ⨝ (σcost<100Catalog )⨝Suppliers))
c) (πsname ((σcolor=redParts) ⨝ (σcost<100Catalog )⨝Suppliers)) ∩ (πsname
((σcolor=greenParts) ⨝ (σcost<100Catalog )⨝Suppliers))
d) (πsid((σcolor=redParts) ⨝ (σcost<100Catalog)⨝Suppliers)) ∩
(πsid((σcolor=greenParts) ⨝ (σcost<100Catalog)⨝Suppliers))
e) πsname ((πsid,sname ((σcolor=redParts) ⨝ (σcost<100Catalog )⨝Suppliers )) ∩
(πsid,sname ((σcolor=greenParts)⨝ (σcost<100Catalog)⨝Suppliers)))