When I explain database indexing to new folks I start with a mini-lecture on card catalogs, complete with images. Even young folks who never saw one can _very_ quickly understand what it's for and how it works. And then when you point out that a database index is pretty much the same thing a light bulb goes off.
"Why does a new index cost disk space?" "It's a whole new wooden cabinet"
"Why is re-indexing expensive?" "Look at all those cards! Each one needs to be regenerated"
"Why does a new index cost disk space?" "It's a whole new wooden cabinet"
"Why is re-indexing expensive?" "Look at all those cards! Each one needs to be regenerated"
And so on.