On Thursday 08 December 2005 22:39, Martin Simmons wrote:
> >>>>> On Wed, 07 Dec 2005 17:06:19 -0500, Ryan Novosielski
> >>>>> <[EMAIL PROTECTED]> said:
>
> Ryan> I don't really understand the description of the red/black binary
> Ryan> tree... I'd appreciate it if you could just explain this a little
> better Ryan> (if you're not too busy, it's clearly not urgent).
>
> It's just a way of storing values so they can be retrieved again
> efficiently. The classic binary tree doesn't guarantee "efficiently" in all
> cases.
Exactly. The nice property of red/black binary trees is that they are always
optimally balanced, which means that searches and inserts are fast. This
comes at the expense of a good amount of extra logic during inserts.
The red/black binary tree classes are now implemented in Bacula, but replacing
the current restore in-memory tree code with red/black binary trees is
another story. Basically the in-memory tree would become a separate binary
tree for each directory. For small directories, it simply costs more space,
but for huge directories, one could have huge savings ...
>
> Goggle finds lots of references to it.
>
> __Martin
--
Best regards,
Kern
(">
/\
V_V
-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems? Stop! Download the new AJAX search engine that makes
searching your log files as easy as surfing the web. DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
Bacula-users mailing list
Bacula-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bacula-users
