B-Trees: Structure, Operations, and Applications

Question 1

What is the primary distinction between B+ trees and B* trees?

Accepted Answer

B* trees maintain a stricter balance criterion compared to B+ trees.

Answer

B+ trees store data in leaf nodes only, while B* trees store data in all nodes.

Answer

B+ trees offer faster search operations than B* trees.

Answer

There are no significant differences between B+ trees and B* trees.

Question 2

Which operation is NOT supported by B-trees?

Accepted Answer

Set union

Answer

Insertion

Answer

Deletion

Answer

Range queries

Question 3

What is the distinction between a structural and a logical B-tree split?

Accepted Answer

A structural split modifies the physical tree structure, while a logical split does not.

Answer

A logical split modifies the physical tree structure, while a structural split does not.

Answer

There is no difference between a structural and a logical split.

Answer

Structural splits occur during insertion, while logical splits occur during deletion.

Question 4

Which of the following is a defining characteristic of B-Trees?

Accepted Answer

Tree height scales logarithmically with key count.

Answer

Nodes contain an equal number of keys.

Answer

B-Trees are only suitable for small datasets.

Answer

Data access in B-Trees is restricted to sequential order.

Question 5

What is the minimum number of keys permitted in a non-root node of a B-Tree of order m?

Accepted Answer

⌊m/2⌋

Answer

m/2

Answer

m/4

Answer

⌊m/4⌋

Question 6

What is the maximum number of keys that can be stored in a B-Tree node with order m?

Accepted Answer

m

Answer

m-1

Question 7

What is the purpose of a B*-Tree?

Accepted Answer

To optimize B-Tree performance for workloads with frequent updates

Answer

To reduce the space overhead associated with B-Trees

Question 8

In a B-Tree with order m, what is the minimum number of keys that must be present in a non-root node?

Accepted Answer

(m-1)/2

Answer

m/3

Question 9

In a B*-Tree, what is the role of the auxiliary pointers?

Accepted Answer

To reduce the number of disk accesses during insert and delete operations

Question 10

In a B-tree, how do you delete a key? Describe the steps and consider the different cases that may arise.

Accepted Answer

Locate the leaf node with the key. If found, delete it and adjust ancestor node counts.

Answer

Find the leaf node with the key and its successor. Replace the key with the successor and delete the successor.

Answer

Find the largest key in the left subtree of the node with the key. Replace the key to be deleted with this key.

Answer

Recursively search the tree to find and delete the key.

Question 11

How can B-tree traversals be utilized effectively for efficiently retrieving elements within a specified range?

Accepted Answer

Conducting an in-order traversal commencing from the leftmost leaf node

Answer

Performing a linear search starting from the root node

Answer

Employing a binary search within each individual node

Question 12

Which property is NOT characteristic of a B-Tree?

Accepted Answer

Insertion and deletion operations have a constant time complexity.

Answer

All nodes have the same number of keys.

Answer

Every leaf node is at the same level (balanced height).

Answer

Can be used to store large amounts of data on disk.

Question 13

During which operation does a B-Tree node split occur?

Accepted Answer

Insertion

Answer

Deletion

Answer

Search

Answer

Update

Question 14

What is the primary purpose of the sentinel node in a B-Tree?

Accepted Answer

To mark the end of the tree

Answer

To accommodate overflow keys

Answer

To balance the tree

Answer

To provide additional search functionality

Question 15

In which application are B-Trees commonly utilized?

Accepted Answer

Database management systems

Answer

File systems

Answer

Operating systems

Answer

Web browsers

Question 16

What is the average time complexity of searching for a key in a B-Tree of height h?

Accepted Answer

O(log h)

Answer

O(h)

Answer

O(n)

Answer

O(n^2)

Question 17

How do the order and node size of a B-Tree affect its performance in terms of storage efficiency, search speed, and update efficiency?

Accepted Answer

A higher order typically improves storage efficiency but may slow down search and update operations.

Accepted Answer

A larger node size typically speeds up search operations but may reduce storage efficiency.

Answer

Both the order and node size have negligible impact on B-Tree performance.

Answer

A lower order and smaller node size always ensure optimal B-Tree performance.

Question 18

Which of the following properties is NOT true about B-Trees?

Accepted Answer

They can be empty.

Answer

They are height-balanced.

Answer

They have a minimum number of keys in each node.

Answer

They are commonly used in database management systems.

Question 19

What is the maximum number of keys that a B-Tree node of order m can contain?

Accepted Answer

m

Answer

m - 1

Answer

m + 1

Answer

2m

Question 20

What is the key difference between a B-Tree and a B+ Tree?

Accepted Answer

B+ Trees store data only in leaf nodes.

Answer

B+ Trees typically have a higher fan-out than B-Trees.

Answer

B+ Trees are not height-balanced.

Answer

There is no difference between B-Trees and B+ Trees.

Question 21

Which of the following is NOT an application of B-Trees?

Accepted Answer

Graph databases

Answer

Database indexing

Answer

File systems

Answer

Caching systems

Question 22

What is the time complexity of searching for a key in a B-Tree of height h?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(h)

Answer

O(h²)

Question 23

Which of the following is a potential disadvantage of using B-Trees?

Accepted Answer

They can be inefficient for storing very large amounts of data.

Answer

They require a significant amount of memory overhead.

Answer

They can be slow to insert and delete keys.

Answer

They are not suitable for real-time applications.

Question 24

What is the key distinction between a B-Tree and a B+ Tree?

Accepted Answer

B+ Trees store data only in leaf nodes, while B-Trees can store data in both leaf and internal nodes.

Answer

B+ Trees have higher fan-out than B-Trees, resulting in improved performance for large datasets.

Question 25

What is the primary advantage of using B-Trees over binary search trees?

Accepted Answer

Enhanced performance, especially for large datasets, due to reduced disk I/O operations.

Answer

Simpler and more straightforward implementation compared to binary search trees.

Question 26

What is a potential drawback of B-Trees?

Accepted Answer

Increased implementation complexity compared to simpler data structures like binary search trees.

Answer

Lower performance for small datasets when compared to binary search trees.

Question 27

In a B-Tree with order 'm' and 'n' leaves, what is its approximate height?

Accepted Answer

log base m of n

Answer

log base 2 of n

Question 28

Which of the following is a common application of B-Trees?

Accepted Answer

Indexing large datasets in database management systems.

Answer

Maintaining sorted collections of data in memory-intensive applications.

Question 29

What is an advantage of using a B* Tree over a traditional B-Tree?

Accepted Answer

Improved write performance due to the separation of data and search keys.

Answer

Reduced memory overhead compared to B-Trees.

Question 30

What is the primary objective of a B-Tree?

Accepted Answer

To efficiently store data on disk, optimizing read and write operations

Answer

To maintain a balanced search tree in memory

Answer

To facilitate efficient range queries on sorted datasets

Answer

To implement a priority queue data structure

Question 31

What distinguishes a B+ Tree from a B-Tree?

Accepted Answer

B+ Trees store data values exclusively in leaf nodes, while B-Trees store data values in all nodes.

Answer

B-Trees offer higher concurrency compared to B+ Trees.

Answer

B+ Trees are suited for disk-based storage, while B-Trees are designed for in-memory storage.

Answer

There is no difference between B-Trees and B+ Trees.

Question 32

What is the time complexity of searching for a key in a B-Tree of height "h"?

Accepted Answer

O(log h)

Answer

O(h)

Answer

O(h^2)

Answer

O(n)

Question 33

Which of the following is an advantage of B+ trees over traditional B-Trees?

Accepted Answer

Both Enhanced search performance and Reduced space overhead

Answer

Enhanced search performance

Answer

Reduced space overhead

Answer

Improved concurrency

Question 34

What is the purpose of a split operation in a B-Tree?

Accepted Answer

To maintain balance when a node overflows

Answer

To merge two adjacent nodes

Answer

To delete a key from the tree

Answer

To insert a new key into the tree

Question 35

What is the time complexity of searching for a key in a B-Tree of order m?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(log m * n)

Answer

O(1)

Question 36

Which property characterizes B-Trees?

Accepted Answer

Height-balanced search trees

Answer

Complete trees

Answer

Superiority to binary search trees for small datasets

Answer

Storage of only integer values

Question 37

What is the primary purpose of B-Trees?

Accepted Answer

Efficient storage and retrieval of large datasets

Answer

Graph creation

Answer

Complex mathematical operations

Answer

Data compression and encryption

Question 38

What type of nodes represent non-leaf nodes in a B-Tree?

Accepted Answer

Internal nodes

Answer

Parent nodes

Answer

Root nodes

Answer

Leaf nodes

Question 39

Define the minimum degree in a B-Tree.

Accepted Answer

The minimum number of children a non-root node must have

Answer

The maximum number of keys a node can store

Answer

The number of nodes in the tree

Question 40

What advantage do B* trees offer over B-Trees?

Accepted Answer

Faster insertion and deletion operations

Answer

Support for more complex data types

Answer

Reduced memory requirement

Question 41

Which application commonly leverages B-Trees?

Accepted Answer

Database management systems

Answer

Natural language processing

Answer

Compiler design

Answer

Image processing

Question 42

Which technique helps maintain B-Tree balance during insertions and deletions?

Accepted Answer

Splitting and merging nodes

Answer

Rotating nodes

Answer

Swapping keys between nodes

Answer

Adding auxiliary nodes

Question 43

What is the primary advantage of using a B-Tree over a binary search tree for storing data on a disk?

Accepted Answer

B-Trees minimize disk accesses by reducing the height of the tree, leading to faster retrieval times.

Answer

B-Trees offer faster insertion and deletion operations compared to binary search trees.

Answer

B-Trees require less memory to store the tree structure compared to binary search trees.

Answer

B-Trees have a simpler implementation and maintenance process compared to binary search trees.

Question 44

In a B-Tree of order 'M', what is the maximum number of keys a non-root node can hold?

Accepted Answer

M - 1

Answer

M / 2

Answer

2 * M

Answer

M

Question 45

Which operation on a B-Tree can potentially trigger a node split?

Accepted Answer

Insertion

Answer

Deletion

Answer

Search

Answer

Traversal

Question 46

What is the key difference between a B-Tree and a B+ Tree?

Accepted Answer

In a B+ Tree, only leaf nodes store data pointers, while internal nodes solely guide the search path.

Answer

B+ Trees do not support deletion operations, unlike B-Trees.

Answer

B+ Trees typically have a higher order than B-Trees.

Answer

B+ Trees are not balanced, whereas B-Trees maintain balance.

Question 47

What does the 'order' parameter in a B-Tree primarily determine?

Accepted Answer

The maximum number of children a node can have, influencing the branching factor of the tree.

Answer

The minimum number of keys a leaf node must contain.

Answer

The maximum height of the B-Tree.

Question 48

In which scenario would a B* Tree be preferred over a B+ Tree?

Accepted Answer

When minimizing storage space utilization is crucial, as B* Trees aim to keep nodes as full as possible.

Answer

When dealing with very small datasets, as B* Trees are most beneficial with large datasets.

Answer

When faster insertion operations are a priority, as B* Trees optimize for insertion speed.

Question 49

What is a defining characteristic of all internal nodes (excluding the root and leaf nodes) in a B-Tree?

Accepted Answer

They function as navigational nodes, guiding the search process towards the desired key.

Answer

They are exclusively used during deletion operations to manage the tree structure.

Answer

They directly store the actual data records associated with the keys.

Answer

They always remain half-full, adhering to a minimum fill factor constraint.

Question 50

Why are B-Trees particularly well-suited for indexing large databases?

Accepted Answer

They significantly reduce the number of expensive disk I/O operations required for data access.

Answer

They are generally easier to implement than other tree structures, making them a practical choice.

Answer

They have a very low memory footprint, making them efficient for memory-constrained environments.

Answer

They support a diverse range of data types, making them versatile for indexing various data.

Question 51

When a node in a B-Tree underflows (has fewer keys than the minimum requirement), what mechanism is employed to maintain the structure?

Accepted Answer

The underflowing node either borrows a key from a sibling node or merges with a sibling node to regain the minimum key count.

Answer

The deleted key is reinserted at a different position within the tree.

Answer

The tree becomes unbalanced and requires complete rebuilding to restore balance.

Question 52

What is the time complexity of searching for a specific key in a B-Tree with a height of 'h'?

Accepted Answer

O(log h)

Answer

O(n log h)

Answer

O(n)

Answer

O(h)