Let’s Invent B(+)-Trees
shachaf.net
shachaf.net
As a layman who doesn't clearly remember B Trees, it would be awesome to have even a sentence at the end, like
...and that's B Trees! Commonly used for storing fields in relational databases, filesystems, and more!
For fellow laymen, https://en.wikipedia.org/wiki/B-tree isn't bad, but is there more?
[1] https://github.com/postgres/postgres/tree/master/src/backend...
> The Sorted Containers internal implementation is based on a couple observations. The first is that Python’s list is fast, really fast. Lists have great characteristics for memory management and random access. The second is that bisect.insort is fast. This is somewhat counter-intuitive since it involves shifting a series of items in a list. But modern processors do this really well. A lot of time has been spent optimizing mem-copy/mem-move-like operations both in hardware and software.
> But using only one list and bisect.insort would produce sluggish behavior for lengths exceeding ten thousand. So the implementation of Sorted List uses a list of lists to store elements. In this way, inserting or deleting is most often performed on a short list. Only rarely does a new list need to be added or deleted.
> Sorted List maintains three internal variables: _lists, _maxes, and _index. The first is simply the list of lists, each member is a sorted sublist of elements. The second contains the maximum element in each of the sublists. This is used for fast binary-search. The last maintains a tree of pair-wise sums of the lengths of the lists.
After reading, I thought to myself, "Hmm... I wonder what else he has written. I'll navigate upwards a level to https://shachaf.net/w "...
It returns a blank page with the letter "w". That actually made me laugh out loud.
"Ah, shucks. Let's go up again."
Returns a non-styled page that reads "Success!".
I don't know why B-trees aren't used more as a purely-functional data structure. Once they get large enough, they don't move around much when changed; there is no rebalancing except on deletes, and even that only affects the direct path to the deleted node.
[1] https://github.com/ar-nelson/schemepunk#b-trees
[2] https://github.com/ar-nelson/schemepunk/blob/master/btree.sl...
This is very similar to persistent hash tries, which are used by purely-functional languages like Haskell. But I designed this B-tree library as an implementation of SRFI 146, which uses a comparison function, not a hash function, to create a key-value mapping.
If you're interested in B-trees being persisted to disk, that's how most databases and most filesystems already work.
[1] https://www.geeksforgeeks.org/persistent-data-structures/
There's a few "levels" of persistence available, just as an aside. Immutability I think corresponds to the ~strongest level, but also means it can be hardest to achieve. One easier version allow only _querying_ old versions of the data structure for instance, no modifications except at the tip. Sometimes that's enough.
For those who don't know about this, here's how it works:
Construct a b-tree in memory ('level 0'). When it reaches a certain size, move it to disk (to L1, level 1) in a compact fashion (by building the tree from the leaf up. There is no need to keep spare space at any L1 node because it is a functional data structure, and won't be directly mutated. The L0-tree in RAM can now be scrapped, and built up from scratch with more insertions. Again, when it exceeds a threshold, the in-memory L0-tree and the on-disk L1 tree from earlier are merged to create a new L1 tree. This goes on until the L1 tree has grown beyond a level-1 threshold size (some k times the L0 size), at which point, the L1 tree is pushed into L2. And so on. L0 is in RAM, L1 and others are on disk.
Lookups are more expensive because multiple trees may have to be consulted, but with a judicious use of multiple cores and bloom filters, that cost can be recouped.
This avoidance of in-place mutations works esp. well with SSDs and other copy-on-write systems.
It has the same tree structure with a lot of children. But the hash is used as key, so they need no balancing. It is just assumed the hash is sufficiently well distributed.
I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think they don't get as much credits as they deserve: logn (which in practice is about the same as "constant" for most values of n one encounters in practice) insertion, lookup, deletion and even append (for position-based trees, with some assumptions). Incredibly simple implementation. And, if immutable (based on shared memory), allows trivial snapshotting, having multiple "concurrent" trees sharing most of their memory.
Anyhow, it's here: https://github.com/alefore/weblog/blob/master/immutable-avl-...
I have a small implementation here (which I use, among other things, to hold all lines in a file, in my text editor): https://github.com/alefore/edge/blob/master/src/const_tree.h
They all have poor memory locality, high overheads, and high indirection. This is kryptonite for typical x86 or ARM CPUs. Unless you're only developing for some tiny embedded CPU with no cache, no branch predictor, and low frequency, such algorithms belong in the dustbin of history.
Practically always, you get better actual performance when using array-based structures such as hashtables, B-Trees, or the like.
Features like snapshotting can be implemented using virtual memory tricks, but is a gimmick rarely used outside of pure functional languages. You might find that simply copying an array when needed for a snapshot is faster than a fancy tree with sharing as a native capability. The exception would be certain dynamic programming scenarios where cloning is very common.
I guess I'll implement an analogous immutable B-Tree structure and run some benchmarks. I suspect you're probably right. I'll probably experiment with different branching factors and tree sizes.
I rely a lot on the trivial (i.e., zero cost) snapshotting for feeding work to background threads. For my workload, having to do deep copies constantly would be prohibitively expensive (and I'd rather not deal with the complexity of explicit locking). That said, I'm now curious to see whether using immutable B-Trees will yield significantly better performance. I suspect they likely will. Exciting. :-)
Thanks again!
However the performance limitations of them have started to show, so there's been work done to switch to B-trees[1].
Not sure if that's true. In addition to the main linux trunk using them, Java 8 included them also as an improvement to their HashMap (I found this by googling), so I don't they are not favored anymore.
Edit: language.
I'm fuzzy on all the current Linux use cases, but do remember one of the main users of rb trees was CFS. It's a neat scheduling algorithm.
Java 8 specifically: HashMap is implemented with linked list chaining. This is already not very performant, but you can only do so much with Java being a reference heavy language. RB trees are used if the bucket chain grows excessively long - so it's addressing an edge case, speeding up some worst case scenarios.
Dense hash tables based on open addressing outperform bucketed chaining. Look also at abseil's swiss table or folly's f14 if you want to see how they've further advanced to take advantage of the hardware.
In general: flat, dense, linear structures are king for performance.
This is definitely not true, implementing array based hashtable is trivial and outperforms in most cases java.utl.HashMap. It's just the decision to have LinkedHashMap (in java 1.2) extending HashMap crippled the latter. The issue has been discussed quite a few times in java core mailing list.
But I still stand by "you can only do so much being a reference heavy language." Unless you stick to purely primitive types, implement the hash table off heap, or Project Valhalla bears fruit, it's hard to get the data layout you'd want for a really good implementation. So I agree it can be better, but it's going to be hard to get to best - hence my comment.
Project Valhalla and structs is something people have been asking for since Java 1.4 or so. Still nowhere near. And indeed, "best" would take a custom implementation, case by case. It's doable, but usually very far from pretty.
On a flip note: HashMap in Java is sort of jack of trades, it's node based which means it has poor memory/caching characteristics - around 36bytes per standard node (compared to ~10 for array backed one) - and Nodes+array tend to be top3 objects in heap dumps. The iteration is sort of 'random' (unlikely LinkedHashMap) which has been a source of lots of issues not manifesting during testing. However, it doesn't degrade in virtually any use case. Normally, I don't use it - either a custom one (CompactHashMap), LinkedHashMap (being the go to hashtable), or ConcurrentHahshMap.
For another consideration: B+-trees (or trees generally) aren’t necessarily the best when the workload is mostly appends to the end of the keyspace. Is there an on-disk data structure that is tuned for mostly-append, rarely-insert workloads? Or how about for insert workloads, where each insert is actually a batch of inserts of a large contiguous range of sorted keys? (I’ve observed that this workload makes LevelDB fall over, so LSM trees aren’t it.)
I'm sure I'm not the only one with that particular implementation, but I'm not aware of any named algorithm/variant for it.
Also a fun approach for an array of sorted numbers is to use bits and have the offset represent the value.
tree is Baum
R tree could be called Raum.
Which means space, which fits, because the tree stores the keys spatially.
How to get around this?
To get around this unfortunate property people invented Log-structured Merge Trees - you keep new part of your data which is easy to insert randomly to and once in a while merge it (as sorted data!) with main data. This way degradation is greatly reduced at the expense of reading speed in case of merge.
BTW, LTMs are a variant of the logarithmic method - a way to create dynamic structures (fast to insert and query) from static ones (slow to insert, fast to query). Even sorted arrays can be made fast for insertion in this way.
Anyway, try to keep your insertion order as sorted as possible. Delay actual insertion into disk data if needed.
The merge operation is fast and cache oblivious. Thus, insertion into a set of these arrays is fast.
Query is not so fast - O(log^2N). But I can direct you to Cache-Oblivious Lookahead Arrays (COLA) paper where a technique to get back to O(logN) complexity for lookup is described.
Or you can simple merge these arrays into one at the bulk insertion end.
Source code (not mine): https://github.com/giannitedesco/cola
Is that true? How are they used (sorted, according to link)? How do B+ differ from B trees?
+ Fast search (log(N))
+ Insert/Delete are fast (O(N) ... Most of the time)
+ Iteration is fast (unlike a hash map or similar)
You could have a look at [0] for a deeper dive.
SELECT * FROM EMPLOYEE, DEPARTMENT WHERE EMPLOYEE.DEPARTMENTID = DEPARTMENT.ID
The naive thing would be to iterate employees and for each one read the corresponding department. However that would mean one disk seek per employee.
Disk seeks on the rotational disks relational dbs were developed for took hundreds of ms to complete. Even today's rotational disks have seeks that take dozens of ms. So doing one seek per join result doesn't work at all. You can add caching to disguise to some extent, but that costs memory.
Compare to B-Trees: You build an index on EMPLOYEE.DEPARTMENTID. That index is also a B-Tree. Because they are sorted, you can just walk both employee index and department table in parallel by id. You only need to do n/k seeks (where k is branching factor of the b-tree). You only need one record worth of caching per table (the one under the current cursor).
Bonus: because the indices are sorted, it's easy to pipeline each seek after the previous to further reduced the latency of the query.
If "building an index" means it's just the indices (not all rows of the table), doesn't that indirection mean an extra seek to get the full row? (I probably have a fundamental misunderstanding here)
But you can sort the second column of the index too. So in our case, the index would be sorted by dept id, then employee id.
deptid empid
1 1
1 3
1 7
1 10
...
2 4
2 5
2 9
...
3 2
3 6
3 8
But we can do better: If there are relatively few departments, the database can put a cursor at the beginning of each run of them:
deptid empid
1 1 <- cursor
1 3
1 7
1 10
2 4 <- cursor
2 5
2 9
3 2 <- cursor
3 6
3 8
This isn't a general solution. If there are zillions of departments and each one has only a handful of employees, this doesn't work. And in modern databases low-cardinality indexes like our dept_emp_id index sometimes use more specialized data structures.
One of the beautiful/crazy things about working on databases is it's a product that promises an abstraction that can't actually be implemented perfectly in all cases. Databases uses all kinds of heuristics internally to decide different strategies to answer queries. And vendors are constantly refining, trying to get closer to an ideal they can never actually reach.
But this particular strategy is a common and important one and an example of why B-trees were so important to early relational systems.
What do you have to contribute that teaches not criticises?