"File Organization & Indexing (B and B+ Trees)" — Practice

Question 1

A block is 2048 bytes and a record is 150 bytes, unspanned. Give the blocking factor and the wasted bytes per block.

Accepted Answer

The blocking factor is the floor of 2048 over 150, which is 13. Thirteen records occupy 1950 bytes, so 98 bytes are wasted per block.

Question 2

Why must a secondary index be dense?

Accepted Answer

The file is not ordered on the indexed field, so records with a given value are scattered and cannot be found by scanning forward from a neighbour. An entry is therefore needed for every record.

Question 3

In a B-plus tree, where do data pointers live and what does that buy?

Accepted Answer

Only in the leaves. Internal nodes carry only keys and tree pointers, so more keys fit per block, the branching factor rises and the tree is shallower.

Question 4

With a 1024-byte block, 9-byte key, 6-byte tree pointer and 7-byte data pointer, compute the B-tree order and the B-plus tree internal order.

Accepted Answer

For the B-tree, 6p plus 16(p minus 1) is at most 1024, giving 22p at most 1040, so p is 47. For the B-plus internal node, 6p plus 9(p minus 1) is at most 1024, giving 15p at most 1033, so p is 68.

Question 5

For the same parameters, compute the B-plus tree leaf order.

Accepted Answer

A leaf holds key and data pointer pairs plus one next-leaf pointer, so 16 times p_leaf plus 6 is at most 1024, giving 16 p_leaf at most 1018, so p_leaf is 63.

Question 6

A B-plus tree has internal order 68 and leaf order 63 and indexes one million records. How many levels and how many accesses per point query?

Accepted Answer

Leaves number the ceiling of 1000000 over 63, which is 15874; the level above needs 234 nodes, then 4, then 1. That is 4 levels, so a point query costs 4 accesses plus 1 for the record, which is 5.

Question 7

A file has 30000 records with blocking factor 10. Compare a successful linear search, a binary search on a sorted file, and a B-plus tree lookup with 4 levels.

Accepted Answer

The file occupies 3000 blocks. Linear search averages 1500 accesses, binary search costs the ceiling of log base 2 of 3000, which is 12, and the B-plus tree costs 5 including the record fetch.

Question 8

Insert 10, 20, 30, 40 into an empty B-plus tree with leaf order 3 and internal order 3. Show the resulting tree and explain why 30 appears twice.

Accepted Answer

The first three keys fill the root leaf. Inserting 40 overflows it, so it splits into a left leaf holding 10 and 20 and a right leaf holding 30 and 40, and 30 is copied up to form the root. It appears twice because a B-plus tree leaf must retain every key while the internal node needs a separator.

Question 9

An extendible hash index has global depth 2. Bucket 00 with local depth 2 overflows, and separately bucket 01 with local depth 1 overflows. Describe each outcome.

Accepted Answer

Bucket 00 has local depth equal to the global depth, so only one directory entry points at it and the directory must double to 8 entries with global depth 3 before the bucket splits into 000 and 100, both at local depth 3. Bucket 01 with local depth 1 is pointed at by two entries, so it splits into two buckets at local depth 2 and one entry is repointed, with no doubling.

Question 10

A table has 500000 records with blocking factor 10 and five secondary indexes. Compare the cost of a point query and an insertion, and give the design consequence.

Accepted Answer

An indexed point query costs about 5 accesses against 50000 for a full scan, a factor of ten thousand. An insertion costs about 2 accesses for the record plus roughly 5 for each of the five index updates, so about 27 instead of 2. Indexes must therefore be chosen against the real query mix, and bulk loads drop and rebuild them.

Practice — "File Organization & Indexing (B and B+ Trees)"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities