On 10 Jul 2001, Juliusz Chroboczek wrote:
> RdB> But I wouldn't use a tree myself; this is almost the same
> RdB> situation as the linux kernel has and it started as a moderatly
> RdB> complex hash table but switched to a dead simple page table when
> RdB> somebody did some timing and profiling.
>
> A page table is a different name for a two-level lazy tree. (Rose by
> a different etc.)
Errr, not really.
A tree has key values on each node which label the various child nodes,
within a node you have to use a search (binary split perhaps as it's
sorted - for a Binary tree the search is rather simple :-) ). For a
paged table there are no keys it's just a normal array with a minor
space optimisation for sparse data.
The difference is most obvious when you 'search' the data structure for
a tree it'll take a page of code even if you limit it to two levels,
for a paged table it's just ...
(table[ind/256]?table[ind/256][ind%256]:-1)
Trees are very good for very sparse data with large sparse keys (only a
small percentage of possible keys are valid keys); a paged table needs
a small fully populated _key_ with data that's usually sparse or clumpy
(tho fully populated data is still efficient unlike with a tree)
--
Rob. (Robert de Bath <robert$ @ debath.co.uk>)
<http://www.cix.co.uk/~mayday>
-
Linux-UTF8: i18n of Linux on all levels
Archive: http://mail.nl.linux.org/linux-utf8/
