26

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)

Improve this question
2
  • Are you asking if they will become obsolete from a database implementation standpoint or in general because the have a lot of other applications outside of database applications.
    – Pemdas
    Commented Oct 18, 2011 at 15:50
  • From a database point of view.
    – Daniel Scocco
    Commented Oct 18, 2011 at 16:52

2 Answers 2

Reset to default
26

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.

Improve this answer
4
  • 1
    Interesting. You gave some good pointers (no pun intended!) to explore this topic further. Thanks.
    – Daniel Scocco
    Commented Oct 18, 2011 at 15:34
  • This MIT course also has information on cache oblivious data structures.
    – dan_waterworth
    Commented Jun 15, 2013 at 16:47
  • Hi, did you mean that B-tree will obsolete, because of cache-oblivious data structures, not because of SSDs? But how about other data structures, like block management in a DBMS?
    – Yang Bo
    Commented Apr 4, 2014 at 3:56
  • @user955091 - I meant because of cache-oblivious data structures (pedantically meaning structures that are optimal in the cache-oblivious model), but I was a bit overexcited about them back then. Other data structures aren't going to disappear any time soon. For one thing, cache isn't the only performance issue - parallelism makes different demands. Besides, needing key-based ordering is often a special case - normally, hash tables are king. It can be hard to see a "randomized" layout as cache-friendly, but one access to directly fetch the item is hard to beat - you don't need locality.
    – user8709
    Commented Apr 4, 2014 at 7:52
3

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.

Improve this answer
4
  • 1
    A hash table is (normally) cache oblivious WRT modelling its performance, but that doesn't mean it's efficient in that model. The problem is that hash functions are normally designed to scatter items "randomly" - that's why hash tables are unordered and also why they have poor locality. That means even if you can identify a sequence of items with adjacent keys, you're unlikely to benefit from reading two or more items per block (SSDs are still block devices).
    – user8709
    Commented Apr 16, 2013 at 21:28
  • 1
    Of course hashing is also sometimes called "key transformation" and the transform doesn't have to be "random" - maybe it's possible to define a hash function that allows for reasonably efficient sequential access (not eliminating the searching - information is lost by the hash function, after all - but minimising it) and gives some locality benefits while still keeping hash collisions rare.
    – user8709
    Commented Apr 16, 2013 at 21:31
  • 1
    A decade later and this answer didn't age well lol. B-Trees are still the primary data structure for persisting data in the potentially most efficient way possible, in a typical relational database. Despite SSDs improving the bottlenecks you mentioned of HDDs, that also only made B-Tree indexes faster too. The search time complexity of a B-Tree is O(log(n)). In the worst case, with base 2, for 1 billion rows indexed in a B-Tree, log2(1 billion) = 40, if the table's rows grew to 1 trillion then log2(1 trillion) = 50. 40 & 50 nodes is a tiny number for any modern computer to seek through.
    – J.D.
    Commented Nov 25, 2022 at 4:05
  • Correction on the above comment. log2(1 billion) = 30 and log2(1 trillion) = 40, even better.
    – J.D.
    Commented Dec 20, 2022 at 5:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.