search

DanielStutzbach / blist

A list-like type with better asymptotic performance and similar performance on small lists
Other
310 stars 36 forks source link

Dynamically allocate space in the root node. #6

Open DanielStutzbach opened 14 years ago

DanielStutzbach commented 14 years ago

Right now, small lists allocate enough space for LIMIT children, even if only one or two are actually needed. For small lists (where the root is a leaf), the memory footprint is terrible compared to an array-based list. The root needs to be able to dynamically choose the number of children. However, it needs to be very careful because hitherto a root node has been treated as a subclass of a regular node. With this change, routines cannot assume that any node has space for LIMIT children.

DanielStutzbach commented 14 years ago

I could use a union to give new meaning to unused fields (such as in the index extension area). For very small lists, some of the space in the "ext" area could be used to store items. I'm not sure if that's worth the effort, though.