I implemented BLink Trees in a tiny stand alone demo.
The algorithm turned out to be a littttttle more
complicated then I thought. So I have not had time
to implement the nio paging system yet.
The big claim to fame for the BLink Tree algorithm
over regular B-Trees is that it allows read and write
multiple threads to access the tree at the same time.
The seminal paper on BLink Trees is
http://lambda.cs.yale.edu/cs424/lect/btree.pdf
This turns out to be really slow.
With the help of some special data structures you lock
single BTree nodes as you move up and down the tree.
The cost of locking is enormous. It is about 10X
slower with fine grain locking turned on then without
locking.
Doing a coarse lock that locks entire tables for a
each query would be a lot faster but it increase the
wait time for some queries. But a 10X speed up would
you notice.
Anyway how keen are you guys to have fine grain
locking? I can't get it to go fast.
If you don't need fine grain concurrency then I may
abandon BLink-Trees and just do BTrees which are
simpler anyway.
I have an implementation (without nio) if you guys
want to look at code.
Oh and with fine grain locking turned off (and no
memory page misses ) the BLink Tree is only 10%
slower then the java.util.TreeMap. Most of that speed
loss is from keeping the BTree nodes in a cache so
they can be used with nio.
Karl
=====
Karl Meissner
...........................................................
: Meissner Software Development, LLC :
: "Software development and project management services." :
: http://meissner.v0.net/resume.htm :
...........................................................
__________________________________________________
Do You Yahoo!?
Yahoo! Tax Center - online filing with TurboTax
http://taxes.yahoo.com/
_______________________________________________
hsqldb-developers mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/hsqldb-developers
