3 ms·
Let me try and give an example. Let's assume we are modelling a non-leaf node which contains long keys and long offsets. We can do it in any of the following wa
by visitor4rmindia 18y ago
Let me try and give an example. Let's assume we are modelling a non-leaf node which contains long keys and long offsets. We can do it in any of the following ways:
|offset0|key1|offset1|key2|offset2|key3|offset3......|
OR
|key1|key2|key3...|offset0|offset1|offset2|offset3...|
OR
|offset0|offset1|offset2|offset3...|key1|key2|key3...|
OR
|count|key3|key1|key7...|offset0|offset1|offset2.....| <== Binary search-able keys
In all of these cases, the data structure is different but the basic B-Tree algorithm remains the same. You can implement the algorithm once (using templates (C++), macros (C), or a weakly typed language (Lisp/Scheme)) and re-use it with any and all data structures that come up later.
EDIT: Forgot offset0
- schtog 18y agohow is Lisp/Scheme weakly typed? It is dynamically typed and strongly too(even though the strong/weak typing definition isn't exactly clear).
- visitor4rmindia 18y agoI'm sorry. You're right - that was a slip-up. I meant a non-static (dynamic) typed language.
- ricky_clarkson 18y agoLisp/Scheme are untyped.
- Hexstream 18y agoNo, they're duck-typed. Types are attached to values, not variables, and for example trying to eval (+ 1 "hi") will throw a proper type exception. You usually don't have to declare types but for example in Common Lisp you can optionally declare types for better performance in speed-critical parts of the code.
- ricky_clarkson 18y agoThey're an implementation of the untyped lambda calculus. What you're thinking of are better named tags, not types.