Question

Consider the Happy Cruise Lines Sailor file shown below. It lists all of the sailors on the company’s cruise ships by their unique sailor identification number, their name, the unique identification number of the ship they currently work on, their home country, and their job title.

	Sailor Number	Sailor Name	Ship Number	Home Country	Job Title
1	00536	John Smith	009	USA	Purser
2	00732	Ling Chang	012	China	Engineer
3	06988	Maria Gonzalez	020	Mexico	Purser
4	16490	Prashant Kumar	005	India	Navigator
5	18535	Alan Jones	009	UK	Cruise Director
6	20254	Jane Adams	012	USA	Captain
7	23981	Rene Lopez	020	Philippines	Captain
8	27467	Fred Jones	020	UK	Waiter
9	27941	Alain DuMont	009	France	Captain
10	28184	Susan Moore	009	Canada	Wine Steward
11	31775	James Collins	012	USA	Waiter
12	32856	Sarah McLachlan	012	Ireland	Cabin Steward

                 Sailor file

QUESTION: Construct a B+-tree index of the type shown in this chapter for the Sailor file, assuming that now there are many more records than are shown above. The file and the index have the following characteristics:

• The file is stored on nine cylinders of the disk. The highest key values on the nine cylinders, in order, are:

                        Cylinder 1: 02653

                        Cylinder 2: 07784

                        Cylinder 3: 13957

                        Cylinder 4: 18002

                        Cylinder 5: 22529

                        Cylinder 6: 27486

                        Cylinder 7: 35800

                        Cylinder 8: 41633

                        Cylinder 9: 48374

• Each index record can hold four key value/pointer pairs.

• There are three index records at the lowest level of the tree index.

Answer 1

Given : To draw B+ Tree for given Sailor file.

Introduction to B+ Tree:

• The B+ tree is a balanced binary search tree. It follows a multi-level index format.
• In the B+ tree, leaf nodes denote actual data pointers. B+ tree ensures that all leaf nodes remain at the same height.
• In the B+ tree, the leaf nodes are linked using a link list. Therefore, a B+ tree can support random access as well as sequential access.

Structure of B+ Tree

• In the B+ tree, every leaf node is at equal distance from the root node. The B+ tree is of the order n where n is fixed for every B+ tree.
• It contains an internal node and leaf node.   

Diagram o B+ Tree:

This is final B+ Tree for Sailor file.And we can also Insert ,delete the tree at beginning , ending and at specific postion when we need to modify the data of particular tree.