B+ Tree

1. UNIVERSIDAD DE SANBUENAVENTURA CALI B+ TREE CESAR ANDRES PALACIOS INGENIERIA DE SISTEMAS

2. B+ TREE

3. B+ Tree B+ trees  is a technique for organizing files indexed. One of this is that all keys are found in the leaves and therefore any path from the root to any of the keys have the same length. B +-trees occupy a little more space than B-trees, and this happens to  be duplication in some keys.

4. Features Formally defines a  B+   tree in the following manner: Each page, except the root, contains between d and 2d elements . Each page, except the root, has between d and 2d + 1 + 1 descendants. M is used to express the number of items per page . The following page has at least two offspring . The leaf pages are all the same level . All keys are in leaf pages . The root keys and interior pages are used as indices .

5. Insertion insertion-B + trees is similar to the process of integration in tree-B. When a key is full (m = 2d). In this case, the affected site is divided into two, distributing the key m+ 1 as follows: "The key in d first page of the left and the remaining d + 1 keys on the right page."A copy of the key environmental predecessor up to page.

6. Insertion ( below ) It may be that the predecessor overflow page again, then you must repeat the above process. It is important to note that the overflow is not a leaf page does not duplicate  keys. The propagation process can get to the root, in which case the tree height can be increased by one.

7. B +  Tree   Clearing Deleting a key is a b + tree is relatively  easy,  since the keys to delete pages are in the leaves. In general must distinguish the following cases: CASE 1 : If removing a key, m is greater than or equal ad then ends the erase operation.  The key  root or internal pages do not change by more than be a copy of the deleted key in the leaves. R emove : key 25 Page A

8. B+ Tree   Clearing CASE 2: If removing a key, then m is less ad must be a redistribution of keys, both the  index and in the pages leaves. R emove : key 27 Page A Page B Page C

9. Webgraphy http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap8/85.html http://www.seanster.com/BplusTree/BplusTree.html http://es.wikipedia.org/wiki/%C3%81rbol-B%2B

10. THANK YOU FOR THE ATTENTION