2 ms·
this is an excellent example of when you'd want to use counted b-trees, but much more generally, they provide a middle ground between arrays and linked lists i
by kragen 2y ago
this is an excellent example of when you'd want to use counted b-trees, but much more generally, they provide a middle ground between arrays and linked lists
in arrays, indexing is fast (one instruction), but insertion and deletion is slow
in linked lists, indexing is slow, but insertion and deletion are fast (≈10 instructions)
(iteration is fast in both, though on modern cpus you have to store multiple items per linked-list node for that to remain true)
in counted b-trees, both indexing and insertion/deletion are fast, though not as fast as in arrays or linked lists: logarithmic time instead of constant time, with a larger constant factor