3 ms·
If you used a hash table you'd be doing a lookup for every single search in addition to the search itself. It'd be better to have nodes in the index include an
by onion2k 12y ago
If you used a hash table you'd be doing a lookup for every single search in addition to the search itself. It'd be better to have nodes in the index include an 'extra stuff' pointer that linked to an object containing whatever else is displayed in addition to the results - the sidebar, alternative search suggestions, etc. Any easter egg info would go in there.
(That said, I don't write software to anywhere near Google scale, so there's probably a much better way.)
- keehun 12y agoThat's what I was thinking, but imagining maintaining an index of Google's scale just boggles my mind.
- willvarfar 12y agoThe cost of a lookup on the term is O(1) with one perhaps two main memory accesses and measured in nanoseconds. The search index is likely a tree, and will be taking a main memory stall every node traversal. There are hundreds of easter eggs. There a trillions of search entries. The cost of even a byte per entry would be massive.