Timeline for Will B-Trees and Other Data Structures Become Obsolete With The Advent of Solid State Drives?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2022 at 5:18 | comment | added | J.D. |
Correction on the above comment. log2(1 billion) = 30 and log2(1 trillion) = 40, even better.
|
|
| Nov 25, 2022 at 4:05 | comment | added | J.D. |
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.
|
|
| Apr 16, 2013 at 21:31 | comment | added | user8709 | 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. | |
| Apr 16, 2013 at 21:28 | comment | added | user8709 | 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). | |
| S Apr 16, 2013 at 20:05 | review | Late answers | |||
| Apr 16, 2013 at 20:19 | |||||
| S Apr 16, 2013 at 20:05 | review | First posts | |||
| Apr 16, 2013 at 20:22 | |||||
| Apr 16, 2013 at 19:48 | history | answered | Wilhelm Van Ende Boas | CC BY-SA 3.0 |