Skip to content

B Tree

Jump to bottom
Battistella Stefano edited this page Jan 31, 2015 · 2 revisions

In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.

For each node are stored at least d keys and at most 2d keys.

Wikipedia

var tree = new BTree(5); //an empty tree with 5 minimum keys for each node

Methods

getIterator()

This method returns an iterator for scanning the tree. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.

var tree = new BTree(5);
var it = tree.getIterator();
for(it.first(); !it.isDone(); it.next()) {
  var item = it.getItem();
  //do something
}

The iterator starts from the most left item of the tree.

Complexity: O(1)

insert(key, item)

This method insert the item into the tree. The item could be whatever you want.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2

Complexity: O(logd+1 n)

search(key, node, callback)

This method search the item relatives to the key in the tree that satisfy the condition represented by the callback function. The search could start from a desired node of the tree but this parameter could be omitted. The search returns undefined if the key there isn't in the tree.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.search(0); //8
tree.search(0, tree.maximum()); //undefined

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the node the iteration is working on.

var tree = new BTree(5);
var callback = function(node) { //this function checks if there is a number lower than 5.
  return node.item < 5;
};
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.search(1, null, callback); //2

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new BTree(5);
tree.insert(0, itemA);
tree.insert(1, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
tree.contains(1, null, callback); //itemA

Complexity: O(log n)

minimum(node)

This method returns the node relatives to the minimum key of the tree. The parameter node is optional, but it's necessary if you desire the minimum key of the tree represented by the node as root.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.minimum(); //8
tree.minimum(tree.maximum()); //2

Complexity: O(log n)

maximum(node)

This method returns the node relatives to the maximum key of the tree. The parameter node is optional, but it's necessary if you desire the maximum key of the tree represented by the node as root.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.maximum(); //2
tree.maximum(tree.minimum()); //8

Complexity: O(log n)

minimumKey()

This method returns the minimum key of the tree.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.minimum(); //0

Complexity: O(log n)

maximumKey()

This method returns the maximum key of the tree.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.maximum(); //1

Complexity: O(log n)

successor(node)

This method returns the node that's the successor in the tree. If the node correspond with the maximum, null will be returned.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.successor(tree.minimum()); //2
tree.successor(tree.maximum()); //null

Complexity: O(log n)

predecessor(node)

This method returns the node that's the predecessor in the tree. If the node correspond with the minimum, null will be returned.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.successor(tree.maximum()); //8
tree.successor(tree.minimum()); //null

Complexity: O(log n)

deleteKey(key)

This method delete the key from the tree.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.deleteNode(tree.maximum()); //tree contains 2

Complexity: O(log n)

contains(key, callback)

This method checks if the tree contains a node whose key satisfies the condition represented by the callback function. The callback could be omitted. In this case the method checks if the node key is simply equal to the key parameter.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.contains(2); //true
tree.contains(5); //false

If you desire a more complex research of a node you need to pass also the callback parameter. The callback must accept the node the iteration is working on. In that case the key parameter could be omitted because it won't be used to evaluate the condition.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var callback = function(node) { //this function checks if there is a node with a item whose value is lower than 5.
  return node.item < 5;
};
tree.contains(null, callback); //true

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new BTree(5);
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
var callback = function(node) { //this function checks if there is an item whose parent is itemA 
  return node.item.parent === itemA;
};
tree .contains(null, callback); //true

Complexity: O(log n)

fullContains(callback)

This method checks if the tree contains a node that satisfies the callback. The search avoid to check the key of the node so the search is made in the entire tree. This affect the performance because the search doesn't reach directly the node. The callback must accept the node the iteration is working on.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var callback = function(node) { //this function checks if there is a node with a item whose value is lower than 5.
  return node.item === 2;
};
tree.fullContains(callback); //true

Complexity: O(n·log n)

getSize()

This method returns the size of the tree so the number of nodes stored.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.getSize(); //3

Complexity: O(1)

clone()

This method returns a clone of the tree. The items inside the node are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old tree. This problem there is not if items are not object.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var clone = tree.clone(); // clone contains 8, 2, 7

Complexity: O(n·log n)

cloneDistinct()

This method returns a clone of the treecontaining only one copy of the same node. The items of the nodes are cloned only if there's a method cloneDistinct() to invoke or at least a method clone(), otherwise they will be shared with the old tree. This problem there is not if items are not object.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(1, 2); //tree contains 8, 2, 2
tree.insert(2, 7); //tree contains 8, 2, 2, 7
tree.insert(3, 7); //tree contains 8, 2, 2, 7, 7
tree.insert(3, 9); //tree contains 8, 2, 2, 7, 7, 9
var clone = tree.cloneDistinct(); //clone contains 8, 2, 7, 7, 9

Complexity: O(n·m)

m: the number of distinct elements stored in the tree. The time required depends strongly from the number of nodes duplicated. If the number of nodes duplicated is very high, then m tend to be near log n (when the tree contains only one distinct node) so complexity will be O(n·log n). If the number of nodes duplicated is very low, then m tend to be near n (when the tree doesn't contain any duplicated nodes) so complexity will be O(n2).

toArray()

This method returns an array that contains the items of the tree.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.toArray(); //[8, 2, 7]

Complexity: O(n·log n)

clear()

This method empty the tree.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.clear(); //the tree is empty

Complexity: O(1)

isEmpty()

This method checks if the tree is empty or not.

var tree = new BTree(5);
tree.isEmpty(); //true
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.isEmpty(); //false

Complexity: O(1)

execute(callback)

This method execute the callback function for each node stored in the tree. The callback must accept the item of the node the iteration is working on. The callback must also return a value to assign to the item.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var callback = function(item) { //this function returns the square for each item
  return item * item;
};
tree.execute(callback); //tree contains 64, 4, 49

In this example we deal with more complex items.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var callback = function(item) { //this function encapsulate each item into an object
  return {x: item, y: item + 2};
};
tree.execute(callback); //tree contains {x: 8, y: 10}, {x: 2, y: 4}, {x: 7, y: 9}

Complexity: O(n·log n)

filter(callback)

This method returns all the items of the nodes that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 5); //tree contains 8, 2, 5
var callback = function(item) { //this function checks if the item is lower than 4 or greater than 6
  return item < 4 || item > 6;
};
tree.filter(callback); //[8, 2];

In this example we deal with more complex items.

var itemA = {parent: null, item: 0};
var itemB = {parent: itemA, item: 1};
var itemC = {parent: itemB, item: 2};
var itemD = {parent: null, item: 3};
var tree = new BTree(5);
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemB
tree.insert(2, itemC); //tree contains itemC
tree.insert(3, itemD); //tree contains itemD
var callback = function(item) { //this function checks if itemA is in the same hierarchy of the item
  while(item.parent || item === itemA)
    item = item.parent;
  return item === itemA;
};
tree.filter(callback); //[itemC, itemB, itemA]

Complexity: O(n·log n)

indexOf(item, callback)

This method returns the first position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the first position where the item is stored. If nothing has been found, the method returns -1.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.indexOf(2); //1
tree.indexOf(9); //-1

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item of the node the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
var callback = function(item) { //this function checks if there is a number lower than 5.
  return item < 5;
};
tree.indexOf(null, callback); //1

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new BTree(5);
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
tree.indexOf(null, callback); //1

Complexity: O(n·log n)

lastIndexOf(item, callback)

This method returns the last position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the last position where the item is stored. If nothing has been found, the method returns -1.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
tree.lastIndexOf(2); //6
tree.lastIndexOf(5); //-1

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item of the node the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
var callback = function(item) { //this function checks if there is a number greater than 7.
  return item > 7;
};
tree.lastIndexOf(null, callback); //4

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new BTree(5);
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
tree.insert(2, itemB); //tree contains itemA, itemB, itemB
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
tree.lastIndexOf(null, callback); //2

Complexity: O(n·log n)

allIndexedOf(item, callback)

This method returns all the positions of the items that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns all the positions where the item is stored.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
tree.allIndexesOf(2); //[1, 3, 6]
tree.allIndexesOf(5); //[]

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item of the node the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.insert(3, 2); //tree contains 8, 2, 7, 2
tree.insert(4, 8); //tree contains 8, 2, 7, 2, 8
tree.insert(5, 6); //tree contains 8, 2, 7, 2, 8, 6
tree.insert(6, 2); //tree contains 8, 2, 7, 2, 8, 6, 2
var callback = function(item) { //this function checks if there is a number lower than 5.
  return item < 7;
};
tree.allIndexesOf(null, callback); //[1, 3, 5, 6]

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var tree = new BTree(5);
tree.insert(0, itemA); //tree contains itemA
tree.insert(1, itemB); //tree contains itemA, itemB
tree.insert(2, itemB); //tree contains itemA, itemB, itemB
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
tree.allIndexesOf(null, callback); //[1, 2]

Complexity: O(n·log n)

getItem(index)

This method returns the item at position index of the tree.

var tree = new BTree(5);
tree.insert(0, 8); //tree contains 8
tree.insert(1, 2); //tree contains 8, 2
tree.insert(2, 7); //tree contains 8, 2, 7
tree.getItem(0); //8
tree.getItem(1); //2

Complexity: O(n·log n)

Clone this wiki locally