How does SQLite work? Part 2: btrees | Hacker News Reader

How does SQLite work? Part 2: btrees

jvns.ca

34 pointstodsacerdoti17 comments

Part one of this[0] is discussed here[1]

[0]https://jvns.ca/blog/2014/09/27/how-does-sqlite-work-part-1-...

[1]https://news.ycombinator.com/item?id=23663071

Reminder: when anyone says B-Tree in the context of databases they mean B+Tree.

And I'll never understand how efficient B+Tree implementations are not in the standard library of every language/runtime.

I can think of 3 main use cases for them:

- databases

- file systems

- hash maps

The first 2 are not something you code everyday, so if you go for that, installing a dep doing it is not a problem.

The last is usually included in all languages.

Why would you need them available in all languages for?

They're very good all around structures when you want to store anything. i.e. good for any container; just requires an orderable key (or one that can support `contains` and then use a GiST). If the key is orderable then you can iterate over spans with better cache locality.

I think they're only used for databases and file systems because those are cases where people actually bother to write them since they care about performance. If they were in the stdlib then they'd be used for many more things.

I get the point, but I rarely find myself in the case I even need an _ordered_ hash map. Despite the fact my language provide one by default.

I can't remember one time in the last decade where I was in need of a _sorted_ hash map.

And if it ever happen I can easily depend install one.

I'm unsure of having something even more general like a b+tree would help.

It's possible that, because I'm not use to have them handy, I don't think about them when I encounter a problem for which they would be perfect.

But I never felt like I missed them.

Can you give me a few examples of problems you them for in the past year?

Was that with a high or low level language?

Let's get all the records from 2020-06-28T10:00:00.000Z to 2020-06-29T09:59:59.999Z and sum the quantity field. Or anywhere you would want to group_by. Or anywhere you might use something like an RDD that partitions the data to compute something for each chunk of data (in parallel) (also after a group_by).

Also, sparse vectors. You don't have a value to store for each index so you use a BTreeMap. I've done this using sentinel values in an array, but that's gross depending on how sparse and how large the vector is.

In Python I would just use a Dataframe (pandas), but in Rust I would use BTreeMap. I wouldn't wish for all languages to have a dataframe type in them since they're such complicated beasts with tricky APIs (pandas and R are such acquired tastes) so I think people can get quite far with B(+)Trees. So that's what I wish was in every stdlib.

I don't know, wouldn't dumping the data into a db easier? If it fits on sqlite, you already have a solution in most languages to this problem.

Technically you would be using a btree, but a higher level interface, like with a fs or hashmap. Which is kinda my point.

I dont say it's not a good DS, but having it in all languages stdlib seems overkill given the tool we have today.

I'm a python guy, and even without panda it has the heapq module which is a b-tree, yet I never really got a reason to use it.

Heapq is a priority queue implemented on a binary tree; not a btree.

> I dont say it's not a good DS, but having it in all languages stdlib seems overkill given the tool we have today.

C++ has map and Java has TreeMap. These are both red black trees (which are equivalent to btrees where k=4). So there's no question of whether there are ordered mapping types in these languages. IMO they'd be better as b(+)rees with a wider fanout. That's all.

Funny, when I saw the title before clicked I thought to myself: "I am sure it's a B+Tree really" :-)

In memory, hashmaps will comfortably beat B(+) trees. If you need to persist data or have too much data for purely in-memory use (and those 2 tend to go together), you tend to reach for some database or the filesystem to as a substrate, which do both very well.

Basically they are not appropriate for most programming use, except that they keep data ordered where a hash won't, and an ordered hash isn't often needed.

ordered containers exist in most standard libraries. e.g. C++ std::map. Java TreeMap. So it's not a question of having containers ordered. But C++ and Java use red black trees (though avl trees satisfy the requirements set by the C++ standard). These are equivalent to BTrees with a small fanout. I would rather have something like B+Tree with an enormous fan out so the use of being ordered (ranged reads) gets better cache coherency.

I know ordered containers exist in some standard libs, question is, how useful are they? Have you ever had a need for one? Because I've decades of programming and I can't recall ever needing one directly (indirectly via a DB, of course, but I mean directly).

What do you do that you feel would benefit from cache locality that in-mem btrees give over other structures? How often have you needed an ordered map at all?

I use ordered structures all the time when I have them. Otherwise I'll approximate with vectors, filling it up and sorting when I'm done.

That seems to miss the point. Ordered containers maintain order. What you're describing is needing ordered results at the end "...and sorting when I'm done". And if you need ordered results only at some end point, it's probably more efficient to accumulate them unsorted then sort them just when needed.

What do you regularly do that needs a data structure that maintains order consistently? A LUT for compiler symbols could be implemented as a binary (or n-ary) tree but that order is incidental; it's only used to get fast lookup. A hash would be faster. I think graph algos may be different but I've never used one, and they tend to use heaps to get an order, but don't need to maintain an ordered collection.

Time Series.

But also prefix lookup. You can do some sweet tricks with trees where lookup on strings can use a prefix and then you get an iterator. You can then use this iterator to read the items until you find one where the prefix doesn't match. I've used this in developing storage systems, but it seems like a useful trick that I might want to use elsewhere.

Thanks, I guess you work in different domain than me. I'll do some reading up on both of these. If you have any pointers, please feel free to post them.

You ask, rust give:

https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...

I have found to have btree/sets included very handy.

Suddenly some hacks around hash maps fade away. For example, sort for presentation or check for min/max, dedup data, etc.. Instead of hand code, pick the proper container and COLLECT:

https://doc.rust-lang.org/std/collections/

(ie: You `.collect` at the end of a iterator into your container of choice. Cool)

I think developers just adapt to whatever is provided not matter if is the real fit or not. So is important to provide a good set of types/structures.

I think all langs must give (at least):

- Int, Float, Decimal

- Bool

- Strings (unicode/utf8)

- Dates!

- Enums or better algebraic types

- Vectors, HashMap, Btree, Sets

Reply on news.ycombinator.com