Re: [help] main memory db

"Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message <news:tO9zb.21$2A3.131_at_news.oracle.com>...

> "Joe "Nuke Me Xemu" Foster" <joe_at_bftsi0.UUCP> wrote in message
> news:1070405687.459566_at_news-1.nethere.net...
> > If the elements in a T-node are kept in order, use Vyssotsky's
> > binary search. When designing the T-node layout, try to make
> > it fit within the CPU level one data cache. This ought to be
> > better than chasing binary tree node pointers all over slower
> > RAM, which will cause the CPU to stall while RAM is copied to
> > cache! While RAM is much faster than disk, level two cache is
> > faster than RAM, and level one cache on the CPU is typically
> > much faster than even the level two cache.
>
> But then, by the same argument, T-Tree should be superior to B-Tree for
> traditional databases as well, because it's just one level lower in the
> memory hierarchy, right?

However, disk is so much slower that minimizing disk access is the absolute priority, while T-Trees might allow simpler inner loops in the implementation, so a reduced number of CPU pipeline stalls (a separate issue from a memory access stall) might make up for the extra memory accesses. Who knows?

OTOH, if the database is a memory-mapped file or VM, a little-used node might have to be swapped in from disk, so we're right back to minimizing the number of nodes that might have to be visited.

--
Joe Foster <mailto:jlfoster%40znet.com>     Greed = God? <http://www.xenu.net/>
WARNING: I cannot be held responsible for the above        They're   coming  to
because  my cats have  apparently  learned to type.        take me away, ha ha!