B+ tree

In computer science, a B+ tree or B plus tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a "block" or "node"). In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.

Reference:
http://en.wikipedia.org/wiki/B%2B_tree

• Consider the following B+ tree with degree d = 2,

which means each node except the root has between 2 and 4 keys, as shown in Figure 1. We label
each node as A0,B0,B1,C0,C1 ... so that you can redraw the tree easily

(1)Different applications with different types of queries may require different indexes on a database
in order to have high efficiency. What type of queries, which your application needs a lot, will
make you choose a B+ tree index over a hash table index? Can you give an example of this type
of queries.(2 points)

Solution When an application needs a lot of range queries, a B+ tree index is preferred. For
example, find all the data entries between 20 and 22

(2)Show the B+ tree that would result from deleting the data entry with key 79 from the original
tree. You MUST redraw the whole tree in your result. But you can use just the labels to denote
those nodes that are unchanged. An example of deleting the data entry with key 6 from the original
tree is shown in Figure 2. If you add descriptions about how the B+ tree is changed, you may get
partial credits if your result drawing is not totally correct. (4 points)

(3) Show the B+ Tree that would result from adding the data entry with key 10 from the original
tree. You MUST redraw the whole tree in your result. But you can use just the labels to denote
those nodes that are unchanged. If you add descriptions about how the B+ tree is changed, you
may get partial credits if your result drawing is not totally correct. (4 points)


webcache.googleusercontent.com/search?q=cache:8vRupC7L9OYJ:https://wiki.engr.illinois.edu/download/attachments/227743489/CS411-F2011-Final-Sol.pdf%3Fversion%3D1%26modificationDate%3D1380470739000+&cd=3&hl=tr&ct=clnk&gl=tr&client=firefox-a