データベースにも使われるb木をjavascriptで実装しました。
あなたは何を検索したいですか？
私は株情報を検索しています。
btree.js
var bNode = (function () {
function bNode(barray, isleaf) {
this.parentNode = null;
this.barray = barray;
this.isLeafNode = isleaf;
this.data = [];
if(isleaf == true) {
this.barray.leaf_nodes.push(this);
}
}
bNode.prototype.split = function () {
var tmp = new bNode(this.barray, this.isLeafNode);
var m = Math.ceil(this.data.length / 2);
for(var i = 0; i < m; i++) {
if(this.data[0].parentNode !== undefined) {
this.data[0].parentNode = tmp;
}
tmp.data.push(this.data.shift());
}
var key = tmp.key = tmp.data[tmp.data.length - 1].key;
if(this.parentNode == null) {
var p = new bNode(this.barray, false);
this.parentNode = tmp.parentNode = p;
this.parentNode.data.push(tmp);
this.parentNode.data.push(this);
p.key = p.data[p.data.length - 1].key;
return p;
}
return this.parentNode.insert_node(key, tmp);
};
bNode.prototype.insert = function (key, value) {
var pos = 0;
for(; pos < this.data.length; pos++) {
if(this.data[pos].key == key) {
this.data[pos].value = value;
return null;
}
if(this.data[pos].key > key) {
break;
}
}
this.data.splice(pos, 0, {
"key": key,
"value": value,
parentNode: this
});
this.key = this.data[this.data.length - 1].key;
if(this.data.length > this.barray.order) {
return this.split();
}
return null;
};
bNode.prototype.insert_node = function (key, node) {
node.parentNode = this;
var pos = 0;
for(; pos < this.data.length; pos++) {
if(this.data[pos].key > key) {
break;
}
}
this.data.splice(pos, 0, node);
this.key = this.data[this.data.length - 1].key;
if(this.data.length > this.barray.order) {
return this.split();
}
return null;
};
bNode.prototype.delete = function (obj) {
obj.node = obj.node.parentNode;
for(; ; ) {
if(obj.node.data.length == 1) {
obj.node = obj.node.parentNode;
if(obj.node == null) {
this.barray.root = null;
return;
}
obj.trace.shift();
} else {
break;
}
}
if(obj.trace[0] == obj.node.data.length - 1) {
obj.node.key = obj.node.data[obj.node.data.length - 2].key;
}
obj.node.data.splice(obj.trace[0], 1);
};
return bNode;
})();
var bArray = (function () {
function bArray(order) {
this.order = 100;
this.leaf_nodes = [];
this.order = order;
this.root = new bNode(this, true);
}
bArray.prototype.restruct = function () {
if(this.leaf_nodes.length > 10) {
;
}
var n = Math.floor(this.leaf_nodes.length / 2);
this.root = new bNode(this, false);
this.root.insert_node(this.leaf_nodes[0].key, this.leaf_nodes[0]);
for(var i = 1; i < this.leaf_nodes.length; i++) {
var leaf_node = this.leaf_nodes[(n + i) * 9998797 % this.leaf_nodes.length];
var ret = this._search(leaf_node.key).node.parentNode.insert_node(leaf_node.key, leaf_node);
if(ret != null) {
this.root = ret;
}
}
};
bArray.prototype.set = function (key, value) {
var node = this._search(key).node;
var ret = node.insert(key, value);
if(ret != null) {
this.root = ret;
}
};
bArray.prototype.set_with_array = function (datas) {
for(var i = 0; i < datas.length; i++) {
var n = i * 9998797 % datas.length;
this.set(datas[n].key, datas[i].value);
}
};
bArray.prototype.get = function (key) {
var node = this._search(key).node;
for(var i = 0; i < node.data.length; i++) {
if(node.data[i].key == key) {
return node.data[i].value;
}
}
return null;
};
bArray.prototype.delete = function (key) {
var node = this._search(key);
var ret;
for(var i = 0; i < node.node.data.length; i++) {
if(node.node.data[i].key == key) {
if(i == node.node.data.length - 1) {
if(node.node.data[0].length == 1) {
node.node.delete(node);
return node.node.data[0].value;
} else {
node.node.key = node.node.data[node.node.data.length - 2].key;
}
}
ret = node.node.data[i].value;
node.node.data.splice(i, 1);
return ret;
}
}
return null;
};
bArray.prototype.delete_in = function (from, to) {
var from_node = this._search(from);
var to_node = this._search(to);
var array = [];
var i = 0;
for(; i < from_node.node.data.length; i++) {
if(from_node.node.data[i].key > from) {
break;
}
}
var now = from_node.node;
for(; ; ) {
if(now == to_node.node) {
break;
}
now.data.splice(i, now.data.length - i);
if(now.data.length == 0) {
from_node.node = now;
now.delete(from_node);
from_node.trace[0]--;
}
for(; ; ) {
from_node.trace[0]++;
if(from_node.trace[0] >= now.parentNode.data.length) {
now = now.parentNode;
if(now == null) {
return array;
}
from_node.trace.shift();
} else {
now = now.parentNode.data[from_node.trace[0]];
break;
}
}
for(; now.isLeafNode == false; ) {
now = now.data[0];
}
i = 0;
}
for(; i < to_node.node.data.length; i++) {
if(i == to_node.node.data.length || to_node.node.data[i].key > to) {
to_node.node.data.splice(0, i - 1);
if(to_node.node.data.length == 0) {
to_node.node.delete(to_node);
}
break;
}
}
};
bArray.prototype.in = function (from, to) {
var from_node = this._search(from);
var to_node = this._search(to);
var array = [];
var i = 0;
for(; i < from_node.node.data.length; i++) {
if(from_node.node.data[i].key > from) {
break;
}
}
var now = from_node.node;
for(; ; ) {
if(now == to_node.node) {
break;
}
for(; i < now.data.length; i++) {
array.push(now.data[i].value);
}
for(; ; ) {
from_node.trace[0]++;
if(from_node.trace[0] >= now.parentNode.data.length) {
now = now.parentNode;
if(now == null) {
return array;
}
from_node.trace.shift();
} else {
now = now.parentNode.data[from_node.trace[0]];
break;
}
}
for(; now.isLeafNode == false; ) {
now = now.data[0];
from_node.trace.push(0);
}
i = 0;
}
for(; i < to_node.node.data.length; i++) {
if(to_node.node.data[i].key > to) {
break;
}
array.push(to_node.node.data[i].value);
}
return array;
};
bArray.prototype.getNode = function (key) {
return this._search(key).node;
};
bArray.prototype._search = function (key) {
var current = this.root;
var found = false;
var array = [];
while(current.isLeafNode == false) {
found = false;
var len = current.data.length;
for(var i = 0; i < len; i++) {
if(current.data[i].key >= key) {
current = current.data[i];
found = true;
array.unshift(i);
break;
}
}
if(found == false) {
current = current.data[len - 1];
array.unshift(len - 1);
}
}
return {
trace: array,
node: current
};
};
return bArray;
})();