B+ Tree in JavaScript

by Graham O'Neill

Introduction

My main objectives for the routine were that it should be:

Pure JavaScript: I didn't want a version that relied on any additional frameworks, libraries or add-on files.

Fast: As a utility function there is no point having it if it isn't reasonably efficient.

Complete: There are lots of "insert only" B-tree solutions, but I wanted mine to have a proper delete function (as opposed to the more normal "lazy delete") as well as providing functions that make the tree useable, such as Seek, Seek Near, Skip, Goto, GoTop, GoBottom.

Understandable: There are solutions that use obscure, complex recursive procedures. Other than displaying the whole tree, where recursion works well, this isn't a problem that is well suited to it. In the cases where you do need to move through the tree performing the same process at different levels (insertion and deletion) you have already identified the path required when you searched for the appropriate leaf in the beginning. A loop works just as well without the additional overhead of recursive function calls. Displaying the tree on the Demo screen is the perfect place to use recursion though.

I've written some notes and a detailed insertion/deletion tutorial to explain in more detail how the functions work. And if you don't want to read all this and just want to play with it, here is the demo screen.

Performance

The demo page has an option to find the total time to insert and seek a set number of random numeric keys. Using this I found the following to be typical speeds with Firefox 20 on my Windows 7, i7-2600 3.4GHz PC:

INSERTTree Order
No. of keys720100
500,000533ms331ms310ms
1,000,0001,236ms769ms764ms
2,000,0002,872ms1,842ms1,784ms
5,000,00010,034ms5,627ms5,279ms
SEEKTree Order
No. of keys720100
500,000119ms92ms120ms
1,000,000245ms189ms241ms
2,000,000525ms392ms497ms
5,000,0001,263ms948ms1,285ms

I also tested it with 10,000,000 keys and found inserts took about 23 seconds for order 8, and 12 seconds for order 100, but at that point the browser became unstable. To be honest, though, if you have that many keys and you're using JavaScript you might want to rethink your approach!

Although these tests and the other routines on the demo page use only integers for the keys, this is only because the display of the results is much easier when keys are quite short. The B+ Tree routines themselves can accept character keys too. Of course, one tree should always use keys of a single type to ensure you get predictable results when comparing them.

Download

If you want to use these routines offline you can download this file:

Zip

This contains the files: btree.html, btree.js (the actual tree processing) and btree-show.js (to display the tree on the screen). The html file contains all the CSS and JavaScript functions related to the demo screen.

It's released under the MIT license, so feel free to use this as you wish but please don't claim it to be your own work, and if you use it in a real application please let me know so I can see it in use. If you find any bugs you can report them by using the Contact Me page.

The JavaScript

Note: don't cut and paste from here as all the < characters will be replaced with "&lt;". Use the Download link above or View Source on the demo page instead. Although the code looks quite long, you'll notice quite a lot of it relates to updating the status indicators (eg. this.eof) rather than the actual B+ Tree.

/*
            B+ Tree processing
              Version 1.0.3
     Written by Graham O'Neill, April 2013
        http://goneill.co.nz/btree.php
*/


// ========== Data structures ==========

leaf = function () {
   this.keyval = [];
   this.recnum = [];
   this.prevLf = null;
   this.nextLf = null;};

node = function () {
   this.keyval = [];
   this.nodptr = [];};

tree = function (order) {
   // Private
   this.root = new leaf();
   this.maxkey = order-1;
   this.minkyl = Math.floor(order/2);
   this.minkyn = Math.floor(this.maxkey/2);
   this.leaf = null;
   this.item = -1;
   // Public
   this.keyval = '';
   this.recnum = -1;
   this.length = 0;
   this.eof = true;
   this.found = false;};


// ========== Method prototypes ==========

// ---------- Leaf nodes ----------

leaf.prototype.isLeaf = function() {return true;};

leaf.prototype.getItem = function (key,near) {
   var vals = this.keyval;
   if (near) {
      for (var i=0, len=vals.length; i<len; i++) {
         if (key <= vals[i]) return i;
      }
   } else {
      for (var i=0, len=vals.length; i<len; i++) {
         if (key === vals[i]) return i;
      }
   }
   return -1;
};

leaf.prototype.addKey = function (key,rec) {
   var vals = this.keyval;
   var itm = vals.length;
   for (var i=0, len=itm; i<len; i++) {
      if (key === vals[i]) {
         itm = -1;
         break;
      }
      if (key <= vals[i]) {
         itm = i;
         break;
      }
   }
   if (itm != -1) {
      for (var i=vals.length; i>itm; i--) {
         vals[i] = vals[i-1];
         this.recnum[i] = this.recnum[i-1];
      }
      vals[itm] = key;
      this.recnum[itm] = rec;
   }
   return itm;
};

leaf.prototype.split = function () {
   var mov = Math.floor(this.keyval.length/2);
   var newL = new leaf();
   for (var i=mov-1; i>=0; i--) {
      newL.keyval[i] = this.keyval.pop();
      newL.recnum[i] = this.recnum.pop();
   }
   newL.prevLf = this;
   newL.nextLf = this.nextLf;
   if (this.nextLf !== null) this.nextLf.prevLf = newL;
   this.nextLf = newL;
   return newL;
};

leaf.prototype.merge = function (frNod, paNod, frKey) {
   for (var i=0, len=frNod.keyval.length; i<len; i++) {
      this.keyval.push(frNod.keyval[i]);
      this.recnum.push(frNod.recnum[i]);
   }
   this.nextLf = frNod.nextLf;
   if (frNod.nextLf !== null) frNod.nextLf.prevLf = this;
   frNod.prevLf = null;
   frNod.nextLf = null;
   var itm = paNod.keyval.length-1;
   for (var i=itm; i>=0; i--) {
      if (paNod.keyval[i] == frKey) {
         itm = i;
         break;
      }
   }
   for (var i=itm, len=paNod.keyval.length-1; i<len; i++) {
      paNod.keyval[i] = paNod.keyval[i+1];
      paNod.nodptr[i+1] = paNod.nodptr[i+2];
   }
   paNod.keyval.pop();
   paNod.nodptr.pop();
};


// ---------- Internal nodes ----------

node.prototype.isLeaf = function() {return false;};

node.prototype.getItem = function (key) {
   var vals = this.keyval;
   for (var i=0, len=vals.length; i<len; i++) {
      if (key < vals[i]) return i;
   }
   return vals.length;
};

node.prototype.addKey = function (key,ptrL,ptrR) {
   var vals = this.keyval;
   var itm = vals.length;
   for (var i=0, len=vals.length; i<len; i++) {
      if (key <= vals[i]) {
         itm = i;
         break;
      }
   }
   for (var i=vals.length; i>itm; i--) {
      vals[i] = vals[i-1];
      this.nodptr[i+1] = this.nodptr[i];
   }
   vals[itm] = key;
   this.nodptr[itm] = ptrL;
   this.nodptr[itm+1] = ptrR;
};

node.prototype.split = function () {
   var mov = Math.ceil(this.keyval.length/2) - 1;
   var newN = new node();
   newN.nodptr[mov] = this.nodptr.pop();
   for (var i=mov-1; i>=0; i--) {
      newN.keyval[i] = this.keyval.pop();
      newN.nodptr[i] = this.nodptr.pop();
   }
   return newN;
};

node.prototype.merge = function (frNod, paNod, paItm) {
   var del = paNod.keyval[paItm];
   this.keyval.push(del);
   for (var i=0, len=frNod.keyval.length; i<len; i++) {
      this.keyval.push(frNod.keyval[i]);
      this.nodptr.push(frNod.nodptr[i]);
   }
   this.nodptr.push(frNod.nodptr[frNod.nodptr.length-1]);
   for (var i=paItm, len=paNod.keyval.length-1; i<len; i++) {
      paNod.keyval[i] = paNod.keyval[i+1];
      paNod.nodptr[i+1] = paNod.nodptr[i+2];
   }
   paNod.keyval.pop();
   paNod.nodptr.pop();
   return del;
};


// ---------- B+ Tree ----------

tree.prototype.insert = function (key,rec) {
   var stack = [];
   this.leaf = this.root;
   while (!this.leaf.isLeaf()) {
      stack.push(this.leaf);
      this.item = this.leaf.getItem(key);
      this.leaf = this.leaf.nodptr[this.item];
   }
   this.item = this.leaf.addKey(key,rec);
   this.keyval = key;
   this.eof = false;
   if (this.item === -1) {
      this.found = true;
      this.item = this.leaf.getItem(key,false);
      this.recnum = this.leaf.recnum[this.item];
   } else {
      this.found = false;
      this.recnum = rec;
      this.length++;
      if (this.leaf.keyval.length > this.maxkey) {
         var pL = this.leaf;
         var pR = this.leaf.split();
         var ky = pR.keyval[0];
         this.item = this.leaf.getItem(key,false);
         if (this.item === -1) {
            this.leaf = this.leaf.nextLf;
            this.item = this.leaf.getItem(key,false);
         }
         while (true) {
            if (stack.length === 0) {
               var newN = new node();
               newN.keyval[0] = ky;
               newN.nodptr[0] = pL;
               newN.nodptr[1] = pR;
               this.root = newN;
               break;
            }
            var nod = stack.pop();
            nod.addKey(ky,pL,pR);
            if (nod.keyval.length <= this.maxkey) break;
            pL = nod;
            pR = nod.split();
            ky = nod.keyval.pop();
         }
      }
   }
   return (!this.found);
};

tree.prototype.remove = function (key) {
   if (typeof key == 'undefined') {
      if (this.item === -1) {
         this.eof = true;
         this.found = false;
         return false;
      }
      key = this.leaf.keyval[this.item];
   }
   this._del(key);
   if (!this.found) {
      this.item = -1;
      this.eof = true;
      this.keyval = '';
      this.recnum = -1;
   } else {
      this.seek(key,true);
      this.found = true;
   }
   return (this.found);
};

tree.prototype.seek = function (key,near) {
   if (typeof near != 'boolean') near = false;
   this.leaf = this.root;
   while (!this.leaf.isLeaf()) {
      this.item = this.leaf.getItem(key);
      this.leaf = this.leaf.nodptr[this.item];
   }
   this.item = this.leaf.getItem(key,near);
   if (near && this.item ==-1 && this.leaf.nextLf!==null) {
      this.leaf = this.leaf.nextLf;
      this.item = 0;
   }
   if (this.item === -1) {
      this.eof = true;
      this.keyval = '';
      this.found = false;
      this.recnum = -1;
   } else {
      this.eof = false;
      this.found = (this.leaf.keyval[this.item] === key);
      this.keyval = this.leaf.keyval[this.item];
      this.recnum = this.leaf.recnum[this.item];
   }
   return (!this.eof);
};

tree.prototype.skip = function (cnt) {
   if (typeof cnt != 'number') cnt = 1;
   if (this.item==-1 || this.leaf===null) this.eof = true;
   if (cnt > 0) {
      while (!this.eof && this.leaf.keyval.length - this.item - 1 < cnt) {
         cnt = cnt - this.leaf.keyval.length + this.item;
         this.leaf = this.leaf.nextLf;
         if (this.leaf === null) this.eof = true;
         else                    this.item = 0;
      }
      if (!this.eof) this.item = this.item + cnt;
   } else {
      cnt = -cnt;
      while (!this.eof && this.item < cnt) {
         cnt = cnt - this.item - 1;
         this.leaf = this.leaf.prevLf;
         if (this.leaf === null) this.eof = true;
         else                    this.item = this.leaf.keyval.length-1;
      }
      if (!this.eof) this.item = this.item - cnt;
   }
   if (this.eof) {
      this.item = -1;
      this.found = false;
      this.keyval = '';
      this.recnum = -1;
   } else {
      this.found = true;
      this.keyval = this.leaf.keyval[this.item];
      this.recnum = this.leaf.recnum[this.item];
   }
   return (this.found);
};

tree.prototype.goto = function (cnt) {
   if (cnt < 0) {
      this.goBottom();
      if (!this.eof) this.skip(cnt+1);
   } else {
      this.goTop();
      if (!this.eof) this.skip(cnt-1);
   }
   return (this.found);
};

tree.prototype.keynum = function () {
   if (this.leaf === null || this.item === -1) return -1;
   var cnt = this.item + 1;
   var ptr = this.leaf;
   while (ptr.prevLf !== null) {
      ptr = ptr.prevLf;
      cnt += ptr.keyval.length;
   }
   return cnt;
};

tree.prototype.goTop = function () {
   this.leaf = this.root;
   while (!this.leaf.isLeaf()) {
      this.leaf = this.leaf.nodptr[0];
   }
   if (this.leaf.keyval.length === 0) {
      this.item = -1;
      this.eof = true;
      this.found = false;
      this.keyval = '';
      this.recnum = -1;
   } else {
      this.item = 0;
      this.eof = false;
      this.found = true;
      this.keyval = this.leaf.keyval[0];
      this.recnum = this.leaf.recnum[0];
   }
   return (this.found);
};

tree.prototype.goBottom = function () {
   this.leaf = this.root;
   while (!this.leaf.isLeaf()) {
      this.leaf = this.leaf.nodptr[this.leaf.nodptr.length-1];
   }
   if (this.leaf.keyval.length === 0) {
      this.item = -1;
      this.eof = true;
      this.found = false;
      this.keyval = '';
      this.recnum = -1;
   } else {
      this.item = this.leaf.keyval.length-1;
      this.eof = false;
      this.found = true;
      this.keyval = this.leaf.keyval[this.item];
      this.recnum = this.leaf.recnum[this.item];
   }
   return (this.found);
};

tree.prototype.pack = function () {
   this.goTop(0);
   if (this.leaf == this.root) return;

   // Pack leaves
   var toN = new leaf();
   var toI = 0;
   var frN = this.leaf;
   var frI = 0;
   var parKey = [];
   var parNod = [];
   while (true) {
      toN.keyval[toI] = frN.keyval[frI];
      toN.recnum[toI] = frN.recnum[frI];
      if (toI === 0) parNod.push(toN);
      if (frI == frN.keyval.length-1) {
         if (frN.nextLf === null) break;
         frN = frN.nextLf;
         frI = 0;
      } else {
         frI++;
      }
      if (toI == this.maxkey-1) {
         var tmp = new leaf();
         toN.nextLf = tmp;
         tmp.prevLf = toN;
         toN = tmp;
         toI = 0;
      } else {
         toI++;
      }
   }
   var mov = this.minkyl - toN.keyval.length;
   frN = toN.prevLf;
   if (mov > 0 && frN !== null) {
      for (var i=toN.keyval.length-1; i>=0; i--) {
         toN.keyval[i+mov] = toN.keyval[i];
         toN.recnum[i+mov] = toN.recnum[i];
      }
      for (var i=mov-1; i>=0; i--) {
         toN.keyval[i] = frN.keyval.pop();
         toN.recnum[i] = frN.recnum.pop();
      }
   }
   for (i=1, len=parNod.length; i<len; i++) {
      parKey.push(parNod[i].keyval[0]);
   }
   parKey[parKey.length] = null;

   // Rebuild nodes
   var kidKey, kidNod;
   while (parKey[0] !== null) {
      kidKey = parKey;
      kidNod = parNod;
      parKey = [];
      parNod = [];
      var toI = this.maxkey+1;
      for (var i=0, len=kidKey.length; i<len; i++) {
         if (toI > this.maxkey) {
            toN = new node();
            toI = 0;
            parNod.push(toN);
         }
         toN.keyval[toI] = kidKey[i];
         toN.nodptr[toI] = kidNod[i];
         toI++;
      }
      mov = this.minkyn - toN.keyval.length + 1;
      if (mov > 0 && parNod.length > 1) {
         for (var i=toN.keyval.length-1; i>=0; i--) {
            toN.keyval[i+mov] = toN.keyval[i];
            toN.nodptr[i+mov] = toN.nodptr[i];
         }
         frN = parNod[parNod.length-2];
         for (var i=mov-1; i>=0; i--) {
            toN.keyval[i] = frN.keyval.pop();
            toN.nodptr[i] = frN.nodptr.pop();
         }
      }
      for (var i=0, len=parNod.length; i<len; i++) {
         parKey.push(parNod[i].keyval.pop());
      }
   }
   this.root = parNod[0];
   this.goTop();
   return (this.found);
};


// ----- Deletion methods -----

tree.prototype._del = function (key) {
   var stack = [];
   var parNod = null;
   var parPtr = -1;
   this.leaf = this.root;
   while (!this.leaf.isLeaf()) {
      stack.push(this.leaf);
      parNod = this.leaf;
      parPtr = this.leaf.getItem(key);
      this.leaf = this.leaf.nodptr[parPtr];
   }
   this.item = this.leaf.getItem(key,false);

   // Key not in tree
   if (this.item === -1) {
      this.found = false;
      return;
   }
   this.found = true;

   // Delete key from leaf
   for (var i=this.item, len=this.leaf.keyval.length-1; i<len; i++) {
      this.leaf.keyval[i] = this.leaf.keyval[i+1];
      this.leaf.recnum[i] = this.leaf.recnum[i+1];
   }
   this.leaf.keyval.pop();
   this.leaf.recnum.pop();
   this.length--;

   // Leaf still valid: done
   if (this.leaf == this.root) return;
   if (this.leaf.keyval.length >= this.minkyl) {
      if (this.item === 0) this._fixNodes(stack, key, this.leaf.keyval[0]);
      return;
   }
   var delKey;

   // Steal from left sibling if possible
   var sibL = (parPtr === 0) ? null : parNod.nodptr[parPtr-1];
   if (sibL !== null && sibL.keyval.length > this.minkyl) {
      delKey = (this.item === 0) ? key : this.leaf.keyval[0];
      for (var i=this.leaf.keyval.length; i>0; i--) {
         this.leaf.keyval[i] = this.leaf.keyval[i-1];
         this.leaf.recnum[i] = this.leaf.recnum[i-1];
      }
      this.leaf.keyval[0] = sibL.keyval.pop();
      this.leaf.recnum[0] = sibL.recnum.pop();
      this._fixNodes(stack, delKey, this.leaf.keyval[0]);
      return;
   }

   // Steal from right sibling if possible
   var sibR = (parPtr == parNod.keyval.length) ? null : parNod.nodptr[parPtr+1];
   if (sibR !== null && sibR.keyval.length > this.minkyl) {
      this.leaf.keyval.push(sibR.keyval.shift());
      this.leaf.recnum.push(sibR.recnum.shift());
      if (this.item === 0) this._fixNodes(stack, key, this.leaf.keyval[0]);
      this._fixNodes(stack, this.leaf.keyval[this.leaf.keyval.length-1], sibR.keyval[0]);
      return;
   }

   // Merge left to make one leaf
   if (sibL !== null) {
      delKey = (this.item === 0) ? key : this.leaf.keyval[0];
      sibL.merge(this.leaf, parNod, delKey);
      this.leaf = sibL;
   } else {
      delKey = sibR.keyval[0];
      this.leaf.merge(sibR, parNod, delKey);
      if (this.item === 0) this._fixNodes(stack, key, this.leaf.keyval[0]);
   }

   if (stack.length === 1 && parNod.keyval.length === 0) {
      this.root = this.leaf;
      return;
   }

   var curNod = stack.pop();
   var parItm;

   // Update all nodes
   while (curNod.keyval.length < this.minkyn && stack.length > 0) {

      parNod = stack.pop();
      parItm = parNod.getItem(delKey);

      // Steal from right sibling if possible
      sibR = (parItm == parNod.keyval.length) ? null : parNod.nodptr[parItm+1];
      if (sibR !== null && sibR.keyval.length > this.minkyn) {
         curNod.keyval.push(parNod.keyval[parItm]);
         parNod.keyval[parItm] = sibR.keyval.shift();
         curNod.nodptr.push(sibR.nodptr.shift());
         break;
      }

      // Steal from left sibling if possible
      sibL = (parItm === 0) ? null : parNod.nodptr[parItm-1];
      if (sibL !== null && sibL.keyval.length > this.minkyn) {
         for (var i=curNod.keyval.length; i>0; i--) {
            curNod.keyval[i] = curNod.keyval[i-1];
         }
         for (var i=curNod.nodptr.length; i>0; i--) {
            curNod.nodptr[i] = curNod.nodptr[i-1];
         }
         curNod.keyval[0] = parNod.keyval[parItm-1];
         parNod.keyval[parItm-1] = sibL.keyval.pop();
         curNod.nodptr[0] = sibL.nodptr.pop();
         break;
      }

      // Merge left to make one node
      if (sibL !== null) {
         delKey = sibL.merge(curNod, parNod, parItm-1);
         curNod = sibL;
      } else if (sibR !== null) {
         delKey = curNod.merge(sibR, parNod, parItm);
      }

      // Next level
      if (stack.length === 0 && parNod.keyval.length === 0) {
         this.root = curNod;
         break;
      }
      curNod = parNod;
   }
};

tree.prototype._fixNodes = function (stk, frKey, toKey) {
   var vals, lvl=stk.length, mor=true;
   do {
      lvl--;
      vals = stk[lvl].keyval;
      for (var i=vals.length-1; i>=0; i--) {
         if (vals[i] == frKey) {
            vals[i] = toKey;
            mor = false;
            break;
         }
      }
   } while (mor && lvl>0);
};

Limitations

Apart from the limit on the number of keys mentioned above, there are also some other restrictions:

Order

The tree must be built with a minimum order of 3 (ie. at least two keys on each leaf and node). I didn't think this was unreasonable as otherwise it isn't really a B+ tree.

Duplicate keys

The routines don't allow duplicate keys. If you really need this facility, I would think the best way to incorporate it would be to change the record pointers on each leaf key into either an array or a linked list. It would be much easier and more effective than allowing for duplicates in the actual B tree structure.

Concurrence

Since JavaScript is a single user, single threaded language I don't need to worry about concurrence at all.

Notes about the Demo

The demo screen shows the tree with each internal node in brown, each leaf in green and the current key in red. It also displays the status flags End of File (eof) and Found, which are updated after each operation. It provides the following operations:

Build new tree

Before you can do anything you have to build a new tree by specifying the order required. The minimum order is 3.

Insert

This will add a specified key value to the tree.

Delete

If a key value is given this will delete that key from the file. If no key is given, the current key is deleted.

Seek / Seek Near

The tree is searched for the specified key. If it isn't found, Seek will return Found as false and eof as true, while Seek Near will return the next highest key value if there is one.

Skip

If no count is given then the next key is made the current key. Otherwise the specified number of keys are skipped over. The count can be positive or negative e.g. Skip(-1) will jump to the previous key. Skip and Skip(1) are identical.

Goto

The current key is selected by counting from the beginning of the tree (or from the end of the file if the parameter is negative).

Top / Bottom

The first or last key in the tree is set as the current key. Top and Goto(1) are identical, Bottom and Goto(-1) are identical.

Pack

Inserting and deleting keys in a tree can mean that there are many nodes that are not completely full. This process will compress the tree into as few leaves and nodes as possible.

Hide / Show From box

The demo screen shows how the last operation changed the tree by displaying what the tree was like before and after that operation. Sometimes it's easier just to see the resulting tree without using up space seeing the original tree, so these options allow you to toggle the display.

Show history

This will display the series of commands you entered to get to the current state. It's probably more useful in offline mode where you can change the html file as then you can cut and paste into the Hardcoded script (see below) to recreate the tree again later.

Run script

The html file has a function called Hardcoded that will run a series of predefined commands. If you are testing changes, this is useful for recreating the initial test tree.

Init random pool

An array with the specified number of random keys is created. No change is made to the tree.

Add random keys

Once the random pool has been created, you can insert a specified number of keys from that pool into the tree.

Random key timer

This will create a random pool with the specified number of keys and will then build a new tree and insert the whole pool into the tree. The total time taken for the build and insertion is displayed. Although a new tree is built, you must still use the Build New Tree option above first, as this specifies what tree order you want to use for the test. To avoid browser timeouts (where the browser will show "Not responding"), timings for up to 2,000,000 keys are performed in one loop and anything above that is split into groups of 1,000,000 keys.

Note that running this multiple times will show progressively slower times. I think this is because the browser has to spend time running a garbage collection process to clean up the previous tree, so the best way of timing is to close the browser and run the html file from Explorer each time.