News for hackers. Stuff that matters.
Re:How we store 400M phone numbers with fast lookup by vidarh on Sunday July 19, 2015 @01:46PM (#9912042)
This is what tries [1] are for, as well as skip-lists [2]. Skip lists for a suitable sized prefix would likely be more space efficient than a trie, but some trie types such as radix-trees [3] with a sufficiently high radix value, could also be quite efficient.

The described approach doesn't seem bad, though it's a bit amusing to see this described as if it's not a very well trodden area of computer science.

[1] https://en.wikipedia.org/wiki/Trie

[2] https://en.wikipedia.org/wiki/Skip_list

[3] https://en.wikipedia.org/wiki/Radix_tree

Re:How we store 400M phone numbers with fast lookup by fiatmoney on Sunday July 19, 2015 @01:50PM (#9912069)
Depending on exactly how they're implemented, tries can give you unacceptable numbers of random disk seeks / uncached memory lookups per read.
Re:How we store 400M phone numbers with fast lookup by vidarh on Sunday July 19, 2015 @01:56PM (#9912107)
They can, but they certainly don't have to, especially not for a dataset like this which is small enough to re-generate offline with data suitably clustered. And certainly no reason why it'd be worse than the describe approach, which isn't really all that conceptually different. What the article described isn't necessarily bad, just unnecessarily ad-hoc when there's plenty of suitable algorithms with well understood tradeoffs and implementations.