Following the advice of the ever-helpful (and ever-correct) tilly, I've converted my indexing program to use DBI::SQLite with excellent results!

Because SQLite is a fully relational database, I was able to strip out all of my relationship handling perl which has been proven to be quite pathological with large databases of related objects. Now, the client application will have to be rewritten, and much of the relationship think time will go over to the read-side of the equation, but I'm hopeful that it won't be a significant issue (client reads can take several seconds to poll through a full hierarchy without becoming a major problem).

So, I believe my performance problems have been solved by exporting all relationship handling to a relational database (imagine that!). Thanks to all who offered up suggestions (especially those who pointed out the potentially pathological issues with handling relationship data as the original code was guilty of doing). The upside to all of my problems has been that the rest of my code is extremely streamlined now, and runs considerably more efficiently than it would have had I gotten the database problem solved right the first time.