| 60,7 → 60,7 |
|---|
| <para> |
| The kernel, as well as userspace, makes use of the hash table implementation with |
| separate chaining. The implementation is very generic in that it forces the user |
| to supply methods for computing the hash index, comparing items with several keys |
| to supply methods for computing the hash index, comparing items against a set of keys |
| and the item removal callback function. Besides these virtual operations, |
| the hash table is composed of a dynamically allocated array of list heads that |
| represent each chain, number of chains and the maximal number of keys. |
| 70,7 → 70,12 |
|---|
| <section> |
| <title>B+trees</title> |
| <para> |
| |
| HelenOS makes use of a variant of B-tree called B+tree. B+trees, in HelenOS implementation, |
| are 3-4-5 balanced trees. They are characteristic by the fact that values are kept only in |
| the leaf-level nodes and that these nodes are linked together in a list. This data structure |
| has logaritmic search, insertion and deletion times and, thanks to the leaf-level list, |
| provides fantastic means of walking the nodes containing data. Moreover, B+trees can be used |
| for easy storing, resizing and merging of disjunctive intervals. |
| </para> |
| </section> |
| |