5 ms·
How does a B-tree make queries fast?
- avinassh 3y ago> To sum up, the key takeaway is to prefer sequential access wherever we can. For spinning disks, this is obvious. But why is sequential access faster on SSDs?
- gniv 3y agoNot just SSD, but in RAM also it's faster, for the same reasons (page-based access to caches). Basically you should always use a B-tree whenever you need the functionality of an STL map.
- avinassh 3y agoI understand it is faster on RAM, but I am asking why IOW what makes it faster to access sequentially on SSD
- gniv 3y agoIt is faster in RAM, on SSD, on HDD, for the same reason: the reads are done in blocks. Even if you want a single byte, the system (the controller) will read an entire block, typically on the order of 100k bytes. So if your B-tree node is all stored in one block, all reads from that node will be fast.
- zerr 3y agoI'd assume at some level of IO, blocks/pages/whole buffers are being read, as opposed to reading bytes one by one. So the sequental access takes advantage of this I suppose.
- wizerno 3y agoTLDR; Garbage Collection. In an SSD, a write operation can only be done when the page is already erased. However, the unit of read/write operations are a page, while the unit of erase operation is a block. That means for a disk write, a naive implementation needs to read the whole block, erase the block, then write updated data back to the block, which is unacceptable. Furthermore, blocks should wear out uniformly, otherwise, the SSD would lose capacity. To tackle these problems, SSD introduces Flash Translation Layer (FTL) which helps to build an illusion of random access device. To achieve this, FTL employs an approach very similar to LSM trees. Writes are always written to new, already erased pages, while in the background, garbage collects (GC) outdated data. FTL needs to keep a map from the user’s logical address to physical address on SSD, both in-memory and persistently. So to answer your question, why are sequential writes are faster than random writes on SSDs? Because the address map table is smaller since new data is consecutive in larger chunks. Garbage Collection is simpler and only metadata needs to be updated. Erasing a block is required anyway.
- avinassh 3y agowhat about sequential vs random reads?
- jasonwatkinspdx 3y agoPredictable prefetching.
- infogulch 3y agoLike sibling said, physical pages are typically much bigger than logical pages in SSDs. Also drives do prediction and sequential access is easy to predict.
- marginalia_nu 3y agoIn practice the difference is much smaller between random and sequential reads, with the caveat that all SSD reads on some level are block operations, so locally sequential access is what make the big difference. Though with mmap the OS may do a speculative async readahead, depending on memadvise.
- marginalia_nu 3y agoAnother neat part is that, for intersecting different B-trees, you can use a technique like this to get very efficient algorithm: https://nlp.stanford.edu/IR-book/html/htmledition/faster-postings-list-intersection-via-skip-pointers-1.html https://nlp.stanford.edu/IR-book/html/htmledition/faster-pos... (Here discussed in terms of skip lists, but they are similar enough that the distinction doesn't matter)
- o11c 3y agoNote that the real primitive is "find nearest [with hint]", which has to be the #1 thing I miss in Python. For B-trees it's only going to be a significant win if the chance of intersection is small, less than about `1/(nodes_per_block)`. For binary trees it's a much bigger win since that becomes 1/2 and binary trees are horrible on cache. Hmm, can you efficiently intersect an arbitrary number of B-trees using the same idea as a heap-merge, but with a max heap instead of a min heap? You'd still have to iterate over all on a match, but as long as 2 input trees don't have an intersection, you don't have to look at the others at all ... or does that become equivalent to just doing them in series?
- marginalia_nu 3y agoA nuance that is important here is that not all accesses are equal within the context of disk reads. B-trees are designed to minimize block reads, not memory operations. I guess there are worst case scenarios with evenly spaced intersections spread out exactly one per block, but in terms of block reads it fundamentally doesn't matter how you intersect two such trees, you'll still have to read all blocks, and that is orders of magnitude slower than comparing the values within. I think the tree structure can be considered cached in real world scenarios; not really relevant to the performance you'll get.
- daveevad 3y agoIt's not that deep.
- mike_hock 3y ago[flagged]
- ukuina 3y agoI enjoyed the breadth of this discussion.
- porridgeraisin 3y agoAlright now, let's restore some order to this thread.
- carlmr 3y agoIt would definitely balance this discussion.
- mirekrusin 3y agoLet's drop it.
- Nevermark 3y agoPondering this discussion, it appears to be an artifact of an open access coroutine. There is no dropping, blocking or locking.
- hinkley 3y agoIt's important to achieve a balance.
- oggyboye 3y agoHow does it work when indexing uuid columns?
- kevingadd 3y agoProbably poorly by default, but you could use a hash of the uuid as a key (to try and more evenly spread the entropy) or key it off a suffix instead of a prefix since iirc that's where most of the entropy lives. In practice if you want good performance and scalability it's important to select keys well.
- hobs 3y agoFor this use case people generally choose sequential UUIDs or they want random ones to prevent hot pages for their inserts.
- deleted 3y ago[deleted]
- LAC-Tech 3y agoVery poorly is my understanding. There's various sequential UUID-like schemes that are more sortable by prefixing with bits of physical time. Off the top of my head, ULIDs and also UUID v7.
- sroussey 3y agoI think this really only matters for clustered indexes.
- charlieyu1 3y agoIs there any other data structures that benefits from hardware?
- omginternets 3y agoArrays come to mind.
- prydt 3y agoLSM trees are a good example of a data structure optimized for memory hardware (both hdds and ssds).
- dicroce 3y agoI always think discussions like this should start with the following: A database with no indexes is slow. Finding a particular row will require a linear search. Adding an index on a column means that your optimizing finding rows by the values of that column. Hence, an index is really a mapping of a particular column's value to the position in the db OF that row (very likely an 8 byte sized integer that is the offset into the file of the row in question). This all means we can implement indexes as b-trees where the keys are the values of a particular column and the value is the file offset of the row with that value. You could envision a simple db format where indexes and the main row file are stored in separate files. In such a database you could drop an index simply by deleting the indexes file (or add one by creating it). The main row file actually has all of the data and so indexes can be recreated if necessary (at expense of course).
- wruza 3y agoYou could envision a simple db format where indexes and the main row file are stored in separate files They already envisioned it in DBF and CDX.
- RaftPeople 3y agoThis is how systems handled it before relational was widely adopted, for example the IBM System 36.
- kevingadd 3y agoI've implemented a high performance btree this way in the past, where each table and each index were separate files (with append-only writes for concurrency). It worked pretty well and wasn't hard to get right, but it had some downsides (in particular, the kernel seemed to struggle with all the paging.)
- louthy 3y ago> a high performance btree then … > the kernel seemed to struggle … What was the struggle? If it’s performance doesn’t that contradict your earlier statement? Genuinely interested in what the issue was, not trying to be a pedant
- gfody 3y ago> It was invented over 40 years ago, yet it is still employed by the majority of modern databases. I wonder how true this is for the top commercial engines (Oracle, MS, IBM, etc.) whose internals are closed source and proprietary. Even a decade ago my experience performance testing Exadata implied some exotic magic at work, ie lookups are way faster than the expected O(log n). More recently while testing SQL Server's ability to join hundreds of tables together the performance was _way_ in excess of what I expected. I can't imagine these things have internals all that similar to say the B+Tree inside MySQL for example.
- kevingadd 3y agoA lot of this comes down to query planners being really good at finding clever ways of doing scans and intersections of indexes, the tables themselves having indexes with a bunch of specialized representations, and the query execution doing very intelligent data traversal with partitioning or even multi-threading. If you sit down and think carefully about your data you can often make even a simple bare-bones B-tree perform fantastically for a query, well in excess of what you'd get out of mysql or sqlite (which are already pretty fast).
- bob1029 3y agoI think the most important takeaway is that the old school RDBMS products are probably more than enough for whatever you are trying to accomplish. Query planners in these are indistinguishable from magic, as should anything that has been forged in the fires of a million production environments for a few decades. I've been playing around with an idea that involves putting sql server at the heart of a game engine, and it is turning into one of the biggest rabbit holes I've ever explored. I thought latency/jitter would be more of a problem but it simply isn't.
- jiggawatts 3y agoOn disk, SQL Server uses only b-trees, unless using the new ColumnStore format. In memory during a query it can use temporary indexes of other types, primarily hash tables and bitmaps. Its performance on ad-hoc complex queries is about as good as it gets, few if any other RDBMS can beat its performance, but under the hood it’s still mostly just doing joins on b-trees!
- cgopalan 3y agoAmidst all these great discussions, I would like to point out that this article really helped me get my head around a B tree and why its a great optimization on top of the Binary Search Tree. Thanks to the author!