あなたは何を検索しますか？〜btree.js

データベースにも使われるb木をjavascriptで実装しました。
あなたは何を検索したいですか？

私は株情報を検索しています。

```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;
})();

```