All of the work in this project is my own!  I have not left copies of my code in public folders on university computers. I have not given any of this project to others. I will not give any portion of this project to others taking this class. I realize that the penalty for turning in work that is not my own can range from an "F" in the class to dismissal from Trinity University. 

                                                                                             Print Name  __________________________

                                                                                              Signature   __________________________

Extra Credit!

_____ Yes, this solution is entirely mine; I did not use any references to derive my solution!
 

                                                                                              Signature   __________________________

Assume M = 5      sizeof(InfoType) = 7,996 Bytes

1] B Tree Node Has __________ Records

2] B+ Tree Node Has __________ Record/Sets

3] B Tree Node Has __________ B Tree Node Ptrs

4] B+ Tree Node Has __________ B+ Tree Node Ptrs

5] B Tree Node Has __________ Actual Number Counters

6] B+ Tree Node Has __________ Actual Number Counters

7] sizeof(B Tree Node) = ______________________ Bytes

8] sizeof(B+ Tree Node) = ______________________ Bytes

9] B Tree has a maximum of ______________________ records in the first/root level.

10] B+ Tree has a maximum of ______________________ records represented in the second level.

11] B Tree has a maximum of ______________________ records in the third level.

12] B+ Tree has a maximum of ______________________ records represented in the Fourth level.

13] B+ Tree has at least ______________________ records represented in the first/root level.

14] B Tree has at least  ______________________ records in the second level.

15] B+ Tree has at least ______________________ records represented in the third level.

16] B Tree has at least ______________________ records in the Fourth level.

17] Every Node of A B Tree, except the root is at least __________ full.

18] B+ Tree has an average of ______________________ records represented in the second level.

19] B Tree has an average of  ______________________ records in the third level.

20] B+ Tree has an average of ______________________ records represented in the Fourth level.

21] Sketch the B Tree Node:

22] Sketch the B+ Tree Node:

Assume M = 101      sizeof(InfoType) = 9,996 Bytes

1] B Tree Node Has __________ Records

2] B+ Tree Node Has __________ Record/Sets

3] B Tree Node Has __________ B Tree Node Ptrs

4] B+ Tree Node Has __________ B+ Tree Node Ptrs

5] B Tree Node Has __________ Actual Number Counters

6] B+ Tree Node Has __________ Actual Number Counters

7] sizeof(B Tree Node) = ______________________ Bytes

8] sizeof(B+ Tree Node) = ______________________ Bytes

9] B Tree has a maximum of ______________________ records in the first/root level.

10] B+ Tree has a maximum of ______________________ records represented in the second level.

11] B Tree has a maximum of ______________________ records in the third level.

12] B+ Tree has a maximum of ______________________ records represented in the Fourth level.

13] B+ Tree has at least ______________________ records represented in the first/root level.

14] B Tree has at least  ______________________ records in the second level.

15] B+ Tree has at least ______________________ records represented in the third level.

16] B Tree has at least ______________________ records in the Fourth level.

17] Every Node of A B Tree, except the root is at least __________ full.

18] B+ Tree has an average of ______________________ records represented in the second level.

19] B Tree has an average of  ______________________ records in the third level.

20] B+ Tree has an average of ______________________ records represented in the Fourth level.

The Buffer is configured to read 30 blocks (1024 bytes each)
sizeof(Key) = 4 Bytes           sizeof(InfoType) = 4,996 Bytes

1] M should be  __________ if using a  B Tree implementation. Show your work!

2] sizeof(B Tree Node) = ______________________ Bytes

3] B Tree has a at maximum of ______________________ records in the first/root level.

4] B Tree has a maximum of ______________________ records in the second level.

5] B Tree has a maximum of ______________________ records in the third level.

6] B Tree has a maximum of ______________________ records in the fourth level.

7] Assume that we will have 150,000,000 records. The B Tree would require no more than

 __________ levels.

8] If your computer can read 10 records per second, the maximum time required to search
 

for any one of our 150,000 B Tree records would be ______________ sec.  Remember, the Root Node is generally kept in memory.

9] M should be  __________ if using a  B+ Tree implementation. Show your work!

10] sizeof(B+ Tree Node) = ______________________ Bytes

11] B+ Tree has a maximum of ______________________ records in the first/root level.

12] B+ Tree has a maximum of ______________________ records in the second level.

13] B+ Tree has a maximum of ______________________ records in the third level.

14] B+ Tree has a maximum of ______________________ records in the fourth level.

15] Assume that we will have 150,000,000 records. The B+ Tree would require no more than

 __________ levels.

16] If your computer can read 10 records per second, the maximum time required to search
 

for any one of our 150,000 B+ Tree records would be ______________ sec. Remember, the Root Node is generally kept in memory.

The Buffer is configured to read 30 blocks (1024 bytes each)
sizeof(Key String) = 21 Bytes           sizeof(InfoType) = 4,996 Bytes

1] M should be  __________ if using a  B Tree implementation. Show your work!

2] sizeof(B Tree Node) = ______________________ Bytes

3] B Tree has a at maximum of ______________________ records in the first/root level.

4] B Tree has a maximum of ______________________ records in the second level.

5] B Tree has a maximum of ______________________ records in the third level.

6] B Tree has a maximum of ______________________ records in the fourth level.

7] Assume that we will have 150,000,000 records. The B Tree would require no more than

 __________ levels.

8] If your computer can read 10 records per second, the maximum time required to search
 

for any one of our 150,000 B Tree records would be ______________ sec.  Remember, the Root Node is generally kept in memory.

9] M should be  __________ if using a  B+ Tree implementation. Show your work!

10] sizeof(B+ Tree Node) = ______________________ Bytes

11] B+ Tree has a maximum of ______________________ records in the first/root level.

12] B+ Tree has a maximum of ______________________ records in the second level.

13] B+ Tree has a maximum of ______________________ records in the third level.

14] B+ Tree has a maximum of ______________________ records in the fourth level.

15] Assume that we will have 150,000,000 records. The B+ Tree would require no more than

 __________ levels.

16] If your computer can read 10 records per second, the maximum time required to search
 

for any one of our 150,000 B+ Tree records would be ______________ sec. Remember, the Root Node is generally kept in memory.

Thought Questions

1] __________ {T/F} An Direct Access AVL Tree is almost always a better solution for an application than a Direct Access Binary Tree.

2] __________ {T/F} An Direct Access B+  Tree is always a better solution for an application than a Direct AVL Tree. [Hint: False!]

3] When would it be more appropriate to to use an AVL Tree than a B+ Tree?

4] When would it be more appropriate to to use an AVL Tree than a B+ Tree?

5] Put The Following In Order From Fastest To Longest With Respect To Time You Think It Would Take Most Programmers To Write New Direct Access Code From Scratch {Use initials!}

AVL Tree [AVL],  B Tree[B-T], B+ Tree [B+T], Single Linked List [DLL], Binary Tree [BT]

6] Put The Following In Order From Fastest To Longest With Respect To Time To Search By Primary Key {Use initials!}

AVL Tree [AVL],  B Tree[B-T], B+ Tree [B+T], Double Linked List [DLL], Binary Tree [BT]

7] Assume that an application has 1,000,000 records and that each record is 5,000 bytes in size. The Key is 4 bytes. Does a B Tree or B+ Tree waste the most space? Explain your answer.

8] B Tree applications require at least ___________ files.

9] B+ Tree applications require at least ___________ files.

Sketch Trees

1] Sketch the B+ Tree Node for M = 5 and the following data

100, 200, 300, 400, 500, 600, 700, 800, 900, 50, 150, 250, 350, 450, 550, 650, 750

2] Sketch the B+ Tree Node for M = 7 and the following data

100, 200, 300, 400, 500, 600, 700, 800, 900, 50, 150, 250, 350, 450, 550, 650, 750, 125, 175, 225, 275,  325, 375,  425, 475,  525, 575, 625, 675,  725, 775,  825, 875,  925, 975