Will B-Trees and Other Data Structures Become Obsolete With The Advent of Solid State Drives?

by Daniel Scocco   Last Updated May 15, 2018 18:05 PM

Many (perhaps most?) database applications today use B-Trees and variations to store data, because this data structure optimizes the read, write and seek operations on a hard disk (and these operations in turn play an important role in the overall efficiency of the databases).

Should Solid State Drives (SSDs) completely outplace traditional hard disks (HDDs), though, could we say that B-Trees and variations will become obsolete, giving room for data structures that are more efficient operating on direct access memory? If so, what will those structures be? (e.g., hash tables, AVL trees)



Answers 3


B-Trees are most often used for database indexes on hard disk, but they have advantages even as an in-memory data structure, given the modern memory heirarchy with multiple layers of cache and with virtual memory. Even if virtual memory is on an SSD, that won't change.

I use an in-memory B+-style multiway tree library that I wrote quite a lot in C++. It can have performance advantages - the reason it was originally written was to try to use cache better - but I have to admit it often doesn't work that way. The problem is the trade-off which means items have to move around within nodes on inserts and deletes, which doesn't happen for binary trees. Also, some of the low-level coding hacks I used to optimise it - well, they probably confuse and defeat the optimiser, truth told.

Anyway, even if your databases are stored on an SSD, that's still a block-oriented storage device, and there's still an advantage to using B-Trees and other multiway trees.

BUT about ten years ago, cache-oblivious algorithms and data structures were invented. These are oblivious to the size and structure of caches etc - they make (asymptotically) the best possible use of any memory heirarchy. B-Trees need to be "tuned" to a particular memory heirarchy to make the best use (though they work fairly well for quite a wide range of variation).

Cache oblivious data structures aren't often seen in the wild yet, if at all, but it time they may well make the usual in-memory binary trees obsolete. And they may also prove worthwhile for hard disks and SSDs as well, since they don't care what the cluster-size or hard-disk cache page size is.

Van Emde Boas layout is very important in cache-oblivious data structures.

The MIT OpenCourseware algorithms course includes some coverage of cache oblivious data structures.

Steve314
Steve314
October 18, 2011 15:29 PM

A priori, yes, most database engines will have to be rewritten since the B-Tree will no longer be the most efficient data structure to store data, given that locality is all important in a hard drive where the disk moves slowly and data is fetched in blocks, meaning that any change to the data needs to:

  1. Move the head to the right location on disk (~10ms).
  2. Wait for the disk to rotate (at 10k rpm, that means 167 rotations per second, but on average we only wait for half a rotation, so ~3ms).
  3. Read the block (~3ms).
  4. Modify in RAM. (~10ns)
  5. Move the head to the right location on disk again (~10ms again).
  6. Wait for the disk to rotate again (~3ms again).
  7. Write the block (~3ms).

That's 10+3+3+10+3+3 = 34 ms

On average, doing the same on an SSD is only 1ms, regardless of the position on the disk.

And since a hashtable is far faster, we could think a hashtable would be a better replacement.

The only problem is that hashtables are not order preserving and therefore it is not possible to find next and previous like Van Emde Boas does.

See:

  1. http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
  2. http://bryanpendleton.blogspot.com/2009/06/cache-oblivious-data-structures.html

Why find next and previous is important? Imagine getting all elements larger than x and smaller than z, you need to use indexes with find previous and find next.

Well, the only problem is that we haven't found hashtables with order preserving abilities. Maybe the size of the bucket in the B-tree will be important but that gets resolved with cache oblivious algorithms.

So I would say this is an open ended problem.

Wilhelm Van Ende Boas
Wilhelm Van Ende Boas
April 16, 2013 19:48 PM

OK. This is not so much an answer as it is an attempt to broaden the scope of the current answers into a more coherent whole. Because, well, within the current answers lies a conundrum.

As I'm sure you are all familiar, databases came into their own once z-indexing became prevalent. At its simplest definition it essentially guarantees a hit on a HDD platter within three touches. This enabled me, and of course very many others, to index and rapidly traverse extremely large datasets across multiple table sets. In a very real sense building an exponentially growing Cartesian join became a none issue 20 years ago, memory not withstanding. Thereby enabling us to return nodes as a subset in under 1 or 2 seconds.

Then came along datasets pushed and held in RAM. These not only worked just fine, but were indeed better, allowing us to further apply different tricks to speed up data recovery.

So, does an SSD behave like data held in RAM? Of course RAM has not gone away either. Does z-indexing still have a roll? Does, say for example, vanilla SQL continue to offer a truly useful roll in data management? I suspect it still does, but I do question whether the old model is now an impediment. Anyone's thoughts would be much appreciated.

Alexander Munro
Alexander Munro
May 15, 2018 17:10 PM

Related Questions


Database Modeling doubt

Updated December 10, 2017 16:05 PM