B+ Tree на Javascript
by Michel Beloshitsky
/** * btree.js - plain javascript b+tree implementation. * * 2010, Michel Belohshitsky * * Placed in public domain. */
function btree(order) {
/* Our tree basic structure. */
var tree = {node:[{leaf:[]}]}
/* Insert value (k-v) in the node or lead "n". Return null or new
k-v pair which we need to insert in parent node. */
function insAtomic (n, k, v) {
var pos, retval, arr = n.leaf || n.node, isNode = n.node !== undefined
/* Find position to insert k-v to */
pos = isNode ? 1 : 0; while (k >= arr[pos] && pos < arr.length) pos+=2
/* Insert k-v */
arr.splice(pos, 0, k, v)
/* Check for order overflow */
if (arr.length / 2 > order) {
/* Split if so */
retval = arr.splice(Math.ceil(order / 2) * 2, arr.length)
if (isNode) {
return [arr.pop(), {node:retval}]
} else {
return [retval[0], {leaf:retval}]
}
}
return null
}
/* Find value by key. Returns
[value, position in leaf, value path]. */
function find(k) {
var curr = tree.node, pos, i, path = [tree]
while (true) {
/* Find desired range in node */
pos = 1; while (k >= curr[pos] && pos < curr.length) pos+=2
path.push(curr[pos-1])
/* If found child is node */
if (curr[pos-1].node) {
/* Continue search */
curr = curr[pos-1].node
} else if (curr[pos-1].leaf) {
curr = curr[pos-1].leaf
/* Else it may be leaf - search leaf for key */
pos = 0; while (k !== curr[pos] && pos < curr.length) pos+=2
/* Return found key or null */
return [curr[pos+1], pos, path]
} else {
/* Wrong way (e.g. possible in {node:[ptr1,key]} case) -
* also null */
return [curr[pos-1], pos, path]
}
}
}
/* Weak deletion here */
function weakDel (k) {
var found = find(k), curr, i
if (!found[0] || !found[2] || !(curr = found[2].pop()).leaf)
return false
/* Delete value */
curr.leaf.splice(found[1], 2)
/* Cascade delete keys if needed */
while (!(curr.leaf || curr.node).length) {
/* Mark object for deletion*/
curr.todelete = true
/* Find link for it in parent */
curr = found[2].pop()
i = 0; while ( !(curr.leaf || curr.node)[i].todelete ) i+=2
/* Delete it */
if (found[2].length || curr.node.length > 1)
(curr.leaf || curr.node).splice(i, 2)
else
curr.node[i] = {leaf:[]} /* Here we handle special case
when deleting from top. Our
tree must has at least
{node:{leaf:[]}} structure so
we should not delete more
objects that we can. */
/* If we are at the top */
if (!found[2].length && curr.node.length == 1) {
/* Rebase tree */
if (!curr.node[0].leaf) {
tree = curr.node[0]
curr = tree
}
}
}
return true
}
function put (k, v) {
var found = find(k), top = found[2].pop(), next
/* Insert and split if needed */
while(next = insAtomic(top, k, v)) {
if (top.leaf)
top.next = next[1]
if (!found[2].length) {
/* Rebase tree case */
top = tree = {node:[top]}
} else {
top = found[2].pop()
}
k = next[0]; v = next[1]
}
}
function first () {
var curr = tree, stack = []
while (!curr.leaf) {
stack.push(curr)
curr = curr.node[0]
}
stack.push(curr)
/* Find compatible output */
return [curr.leaf[1], 0, stack]
}
function iterate(s, e, cb) {
var found = s !== null ? find(s) : first()
/* Find first key */
if (found) {
var part = found[2].pop()
var pos = found[1]
cb('start')
} else {
cb('error', 1)
}
while (part.leaf[pos+1] !== undefined) {
if (part.leaf[pos] > e || (part.leaf[pos+2] === undefined && !part.next))
return cb('end')
cb('k-v', part.leaf[pos], part.leaf[pos+1])
if (part.leaf[pos+2] !== undefined) {
pos +=2
} else {
part = part.next; pos = 0
}
}
cb('end')
}
/* Public interface.
Members used for debug commented out. You may enable it again,
for e.g. look at internal structure or better understandance how
staff works. */
return {
put: put,
get: function (k) { return find(k)[0] },
del: weakDel,
iter: iterate,
// f:first,
// find: find,
// insAtomic: insAtomic,
// tree: function () { return tree }
}
}
Игры с map-reduce продолжаются. На этот раз написано то, что ляжет в основу хранилища данных для моего assou.
Осталось лишь продумать механиза синхронизации всего этого дела в файлы и можно будет выпускать на волю.
Смущает лишь отсутствие у меня профильного образования: наверняка я уже где-то прокололся, и проколюсь еще раз. Но экспериментировать-то с другой стороны мне это не мешает.
Запустил в консоли разработчиков хромиума нехитрое
var bt = btree(16), i for (i = 0; i < 1000000; i++) bt.put(i,'r'+i)
Памяти заняло все это хозяйство 133Мб. Не так много, учитывая что простой хэш из миллиона подобных элементов занял 86Мб.
Потом запустил:
for (i = 0; i < 300000; i++) bt.del(i)
Хром подождал минуты 2 и освободил пропорциональный кусок памяти. Сборка мусора работает, это хорошо, значит безумная идея близка к реализации.
Сейчас даже вижу несколько путей по повышению производительности этой реализации. За исключением переписывания на ЯП больше яваскрипта подходящем для таких целей (это неспортивно) можно искать в узлах дерева не при помощи while (как делается сейчас), а бинарным поиском. Это улучшит произовдительность на деревьях большого порядка btree(N), где N ~ >= 40. Но пока есть дела поважнее, я просто запишу здесь, чтобы не забыть.
Еще можно поработать с удалением: сейчас реализован т.н. “слабый” алгоритм удаления – узел удаляется только когда он полностью пуст. Есть и другие подходы.
