[elephant-devel] using btrees or not using btrees

Robert L. Read read at robertlread.net
Thu Apr 20 02:37:41 UTC 2006


Dear Aycan,
    I believe you are describing a problem that in principle has an easy
to understand solution:

The bigger the date object you are dealing with, the more individual
Elephant objects you
problaby want to use to represent it.
 The problem is that one can make a legitimate design decision about
when an object
which is not completely monolithic should go in one object, or many.

    Consider for example, strings about 100 bytes long.  The string is a
primitive object; 
there is no reason to represent it as more than one object in the
Elephant store.  Now consider
a collection of about 10 strings.  This collection could be represented
as 10 elephant objects,
or 1 elephant object which happens to be a list (or some other
collection) of objects.

    In the application I am working on, I use both techniques for
relatively small collections.
That is, sometimes I store lists (of up to 100) strings directly into a
single object.  In other
cases, I would take the 100 objects and give them each a separate
existence (like your
solution 1 below, sort of).  I tend to be a bit cavalier with respect to
performance until
it trips me up; so if you force me to draw a line I would say "Don't put
more than 1000 objects
into an Elephant database as a single object."  One could argue that
this should be lower.
    Here is how I would write these two different ideas:
(open-store *testbdb-spec*)

(setq nodes (add-to-root 'nodes (make-indexed-btree)))
(dotimes (i 100) 
  (setf (get-value i nodes) (* i i)))
(ele::dump-btree nodes)
k 0 / v 0
....lots of lines deleted (98)
k 99 / v 9801
(setq nodelist nil)

(dotimes (i 100)
  (progn
    (push (* i i) nodelist )
    (add-to-root 'nodes nodelist)))
    (get-from-root 'nodes)
(9801 9604 9409 9216 9025 8836 8649 8464 8281 8100 7921 7744 7569 7396
7225
 7056 6889 6724 6561 6400 6241 6084 5929 5776 5625 5476 5329 5184 5041
4900
 4761 4624 4489 4356 4225 4096 3969 3844 3721 3600 3481 3364 3249 3136
3025
 2916 2809 2704 2601 2500 2401 2304 2209 2116 2025 1936 1849 1764 1681
1600
 1521 1444 1369 1296 1225 1156 1089 1024 961 900 841 784 729 676 625 576
529
 484 441 400 361 324 289 256 225 196 169 144 121 100 81 64 49 36 25 16 9
4 1 0)
T
ELE-TESTS> 

    The real question is: would you rather change an item in this set by
changing the 
list, or by treating it as a btree?
    As the list gets larger and larger, it becomes more and more
reasonable to 
user a btree, and less and less reasonable to use a giant list --- but
even then,
never optimize until you have to.

On Wed, 2006-04-19 at 22:47 +0300, Aycan iRiCAN wrote:

> Hi,
> 
> What is the difference between 'using a btree for items' and 'using an
> object to hold items'?
> 
> Say we have a node class. In the first method, I'm creating objects
> and adding them to a btree.
> 
> (add-to-root 'nodes (make-indexed-btree))
> (dolist (item (create-100-node))
>   (setf (get-value 'key 'nodes) item))
> 
> Now I can use cursors and indexes to reach nodes. In the second
> method, I'm using an objects slot to hold nodes.
> 
> (add-to-root 'nodes (make-instance 'node-container :nodes '()))
> (dolist (item (create-100-node))
>   (push item (nodes (get-from-root 'nodes))))
> 
> Because of ease of use and maintainability, we're thinking that the
> second method is better than the first method. We can get a backup
> with a single cl-store call, we can easily walk the structure
> etc.
> 
> Any ideas?
> 
> Best Regards.
> 
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/elephant-devel/attachments/20060419/21271a58/attachment.html>


More information about the elephant-devel mailing list