The title given to this article is incorrect due to technical limitations. The correct title is B+ tree.

Contents

1 Introduction 2 Algorithm 2.1 Insertion 2.2 Deletion 3 External Links

Introduction

A B+ tree is a dynamic, multilevel index with maximum and minimum bounds on the number of keys in each node.

B+ tree is a variety of B tree. But, unlike B tree, all data are saved in the leaves. Internal nodes contain only keys and tree pointers. All leaves are at the same lowest level. Leaf nodes are also linked together as a linked list to make range queries easy.

The maximum number of keys in a record is called the order of the B+ tree.

The minimum number of keys per record is 1/2 of the maximum number of keys. For example, if the order of a B+ tree is n, each node (except for the root) must have between n/2 and n keys.

The number of keys that may be indexed using a B+ tree is a function of the order of the tree and its height.

For a n-order B+ tree with a height of h:

• maximum number of keys is <math>n^h<math>
• minimum number of keys is <math>2(n/2)^{(h-1)}<math>

Algorithm

Insertion

• step 1. search the tree, to find out the bucket for the new data
• step 2. if the bucket is not full, insert the record there, otherwise, split the bucket.
• step 3.
• step 4.
• step 5. Profit!

...

Deletion

External Links

http://www.seanster.com/BplusTree/BplusTree.html