Binary Trees As The Database Design!


More Database Design Mistakes To Avoid

One design that I saw at an interview, was highly unusual.   There was a diagram on the white board.  Inside the database were a number of other boxes, each representing a different subsystem.  I’d never seen anything like it.

We talked about designing the database model for good performance.  We certainly seemed to be on the same page. But then he sat me down at a computer, and had me do a test.  There were a lot of Recursive Ids and parent Ids.  For a given ID, find all the other keys associated with it.

The database “design” was a binary tree, and the test was to traverse the tree!

Binary Trees in the Database

The nodes in the binary trees were actually being used for both storage, and indexing!  In order to find any data, you had to write a routine to traverse the tree. That is, instead of using standard tables, and standard SQL Select statements, with Where clauses to filter the rows.

What could be done in a single SQL statement, you actually had to write 3GL programs to do!

Result:

There were serious performance issues.  As I mentioned in my tuning presentation, it is thousands of times faster to read memory, than read from disk.  Traversing binary trees may work fast in memory.  But the way it was implemented here, would have been thousands of times slower.  For every node (row equivalent) found, there would be a separate random disk access. All these reads would happen recursively, one by one, as opposed to all at once in a batch.

The binary trees became infrastructure, not the product.  Instead of using the database to do some real work, you spent most of your time struggling with the infrastructure.  Lots of time, work, and money, for a lot worse results.

Years later, I asked the recruiter whatever happened with this position.  They hired a guy from a big shop, prestigious company.  But it went very poorly. Things didn’t get done. It didn’t last long.  Can you imagine the discussions, and the wasted people time?

Correction:

Don’t try to reinvent the wheel.  Oracle, Sybase, and SQL Server all have armies of developers putting serious amounts of research, development, and support into the SQL language.  Make use of it.

Learn standard database design concepts and SQL.  Or delegate the architecture and database design to someone who does understand them.

If it makes sense, use Oracle’s Index Organized Table.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: