B-trees for databases in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a B-tree in the context of databases?

A B-tree is a balanced tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. It is widely used in databases to organize and quickly access large amounts of data stored on disk.

intermediate

Why are B-trees preferred for database indexing over binary search trees?

B-trees are preferred because they reduce the number of disk reads by having nodes with many keys and children, which means the tree is shorter and wider. This structure minimizes slow disk access, making data retrieval faster compared to binary search trees that have many levels.

beginner

What does it mean that a B-tree is 'balanced'?

A B-tree is balanced because all leaf nodes are at the same depth. This means every path from the root to a leaf has the same length, ensuring consistent and predictable access times for all data entries.

intermediate

How does a B-tree handle insertions when a node is full?

When a node is full, the B-tree splits the node into two nodes and moves the middle key up to the parent node. This splitting may propagate up the tree, keeping the tree balanced and maintaining its properties.

beginner

What is the main advantage of having multiple keys in each node of a B-tree?

Having multiple keys per node reduces the tree's height, which means fewer disk accesses are needed to find a key. This improves performance because accessing disk is slower than accessing memory.

What property ensures that all leaf nodes in a B-tree are at the same level?

A Recursion

B Balance

C Uniqueness

D Ordering

The balance property of B-trees means all leaf nodes are at the same depth, ensuring consistent access times.

Why do B-trees have nodes with multiple keys?

A To reduce tree height and disk reads

B To make the tree binary

C To store duplicate keys

D To increase tree depth

Multiple keys per node reduce the height of the tree, which lowers the number of disk accesses needed.

What happens when a B-tree node becomes full during insertion?

A The node splits and the middle key moves up

B The node deletes the oldest key

C The tree becomes unbalanced

D Insertion is rejected

When a node is full, it splits into two nodes and the middle key moves up to maintain balance.

Which of these is NOT a typical operation supported efficiently by B-trees?

A Search

B Deletion

C Sorting all keys in linear time

D Insertion

B-trees support search, insertion, and deletion efficiently, but sorting all keys in linear time is not guaranteed.

What is the main reason B-trees are used in databases?

A To simplify programming

B To use less memory

C To store images

D To minimize slow disk access

B-trees minimize disk reads by having a balanced, wide structure, which speeds up database queries.

Explain how a B-tree maintains balance and why this is important for database performance.

Think about how the tree grows and stays even.

Describe the advantages of using B-trees over binary search trees in database indexing.

Focus on how data is stored and accessed on disk.