News for hackers. Stuff that matters.
Re:Binary Search Reconsidered (2018) by ComputerGuru on Friday December 25, 2020 @02:09PM (#25538326)
The problem with eytzinger representation is that it is infinitely less useful, and really can only be used as write-once read-many lookup or cache but not as primary storage that is also a cache because it is no longer contiguous.

eg Etyzinger is awesome, but in most real world usage something like this is far more practical and ultimately performant: Faster Lookups, Insertions, and In-Order Traversal Than a Red-Black or AVL Tree [0].

[0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-...

Re:Binary Search Reconsidered (2018) by tehjoker on Friday December 25, 2020 @03:15PM (#25538714)
You're right about that, but I recently ran into a situation where I had to process about a TB of data repeatedly in that configuration. As a serialized file format, Eytzinger rocked. The IO cost probably dominated, but there was no reason not to use it.