Question

Consider a B-tree allowing splits and free-on-empty. Please show an example of these operations on a data structure containing 15 data items, a fanout of three, and at most three data items per node. Also give the search algorithm (use a give-up scheme).

Answer 1

B-Tree showing split:

This algorithm splits a node only when it is necessary. We first recursively call insert for appropriate child of node (in case of non-leaf node) or insert it into node (for leaf node). If the node is full, we split it, storing new child entry in newEntry and new parent key in val. These values are then inserted into the parent, which recursively splits itself in case it is also full.

Example:

Consider if we insert number 1 to 15 in a tree it become.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Then we insert 16, the node is full. Hence it is split into two nodes making 8,9,10,11 as parent.

1

2

3

4

5

6

7

8

9

10

11

11

13

14

15

16

B-Tree showing Free-at-empty:

The first type allows B-tree nodes to become arbitrarily small (i.e., contain as few as one entry). When a node becomes empty, the space is freed and the delete is propagated upwards. We call this type of B-tree a free-at-empty B-tree. Free-at-empty B-trees.

Example:

5 is a leaf node and if we delete 5 follow the below B-Tree. 8,9,10,11 are the Parent node.

1

2

3

4

6

7

8

9

10

11

11

13

14

15

16

Algorithms:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure