Indexing structures for files II

Question 1

What are some malfunctions related to the binary tree structure

Answer 1

if the tree is in storage, occupying more than one block, there is the risk of thrashing or heavy caching.

Question 2

Describe a search field in a search tree

Answer 2

Each search field has the search value (index value) and a pointer to the associated record in storage (a record pointer or block pointer, depending).

Question 3

What is the need for balancing

Answer 3

Balanced Binary trees are computationally efficient to perform operations on.

Question 4

What is a B-Tree and what is it used for

Answer 4

A b-tree is known as balanced sorted tree.
* It is used for external sorting. External sorting is done when data values cannot fit into the main memory.

Question 5

What conditions of a B-Tree are necessary to reduce disk access

Answer 5

i. The height of the tree must be kept minimal
ii. There must be no empty sub-trees above the leaves of the tree
iii. Leaves of the tree must be at the same level
iv. All nodes except the leaves must have some minimum number of children

Question 6

Give five properties of a B-tree of order M

Answer 6

i. Each node has a maximum of M children and a minimum of M/2
ii. Each node has (M-1) Keys
iii. Keys are arranged in ascending order. All the keys in the subtree to the left of a key are smaller than the key(Predecessor).All the keys to the right are greater than the value of the key(Successor)
iv. When a key is inserted into a full node, the node is split into two nodes, and the median value is inserted in the parent node.
v. All leaves are on the same level i.e no empty subtree above the leave node