Databases (real databases) are using indexing technology that's been proven over not just years but decades of use and refinement. log2(500000000) is still only 28. Double that and it's only 29. And these databases' indexes are typically btrees with much higher branching factors than 2.
One of my favorite articles on this is Dennis Forbes' "The Impact of SSDs on Database Performance and the Performance Paradox of Data Explodification" (http://www.yafla.com/dforbes/The_Impact_of_SSDs_on_Database_...).
An SSD is on par with a 15K disk, but delivers 10X the perf, throw 10 SSDs in an array and you've got what used to cost $100,000 for about $5K
So load half a billion rows but don't update it too often!
What's impressive now is not the software but that the hardware is so cheap.