It's fundamentally just a big array of one entry per block space. It was never too big for an average computer to handle - otherwise Minecraft wouldn't have been able to exist yet (maybe that's why it didn't exist until the time that it did) but they've gotten a lot less efficient since then, in the name of flexibility.

Before Minecraft existed I played Cube 2 on "coop edit" mode. Its world structure is an optimization you might be interested in: it represents the whole game world (of fixed size) as an octree. So the map starts as a node with 8 child slots (one for each corner of a cube); each is either completely solid, completely empty, or another node, recursively down to some maximum depth. Therefore Large empty areas and large solid areas are stored in about the same amount of space as small empty areas and small solid areas.