As soon as you introduce an SQL layer to your app, your complexity goes to a higher order of magnitude, making it that much harder to debug and troubleshoot.
That's hardly true in all cases. Depending on the situation, the "layer of complexity" introduced by your having to build your own data structures is often far worse than whatever is introduced by using an sql database. If you're using a good ORM, it might not really be "complex" at all.
I don't mean this to argue that a db is always good, but I'd guess one of the reasons that people use a database even when it's inappropriate is precisely because it seems less complex.
How can you build an application without data structures anyway? If you ever load data from a database, it's loaded into a data structure of some kind.
Of course, if you're using a bunch of elaborate ORM stuff, I suppose it might build your data structures without you ever really seeing them. Is that what you meant?
Basically: more precisely, that modern database APIs (not just ORMs) can hide much of the complexity of using an sql database, so that it seems neither "elaborate" nor "a higher order of magnitude" more complex to the programmer to build, test or debug. And since modern database layers often give you tools to help build data structures, it might seem simpler to use those tools than to build something without them.
I don't mean this to argue that a db is always good, but I'd guess one of the reasons that people use a database even when it's inappropriate is precisely because it seems less complex.