Depth first or breadth first ordering in binary search trees?

Question

Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array.

The binary tree is full on all levels except possibly the last level, where it is filled from left to right.

Specifically index 0 is the root node, and to get to a left child, you multiply current index by 2 and add 1. To get to a right child you multiply current index by 2 and add 2.

Going this route, as i understand it, the node order is breadth first.

I've seen people mention that depth first is better (in a paper about parallel GPU bvh construction), and was wondering, is there a good reason to choose depth first over breadth first, or is it highly dependent on specific usage patterns?

Answer 1

There's a paper on this: Khuong and Morin. Array Layouts For Comparison-Based Searching

They compare the Eytzinger, B-Tree, Van Emde Boas, and sorted array layouts and conclude that Eytzinger works best. The reasons are fairly complex, since things like simple address arithmetic and branch predictability combine with memory prefetch and processor features like speculative execution. They also rely on doing a fair amount of extra work by prefetching blocks which have only a small chance of matching the search argument.

However they do give a clear exposition of each mechanism.

Answer 2

Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so big that they can't fit into memory caches. When that happens, if you've laid out the memory in a BFS order, then going from one layer to the next will almost always cause a cache miss because the memory fetched for the first layer won't include the node from the next layer in it. In other words, every link followed will cause a cache miss. On the other hand, if you use DFS order, then the memory for the nodes will have the nodes broken apart into smaller chains of nodes corresponding to the paths taken by DFS. If you do lookups in a way that follows those chains, it's possible that you'll have no cache misses at all when going from one node to the next, which can dramatically speed up lookups.

The ordering I've actually heard most for making cache-friendly BSTs is the van Emde Boas layout, which is formed as follows:

• If the tree has height two or less, lay it out in DFS or BFS order (they're the same here).

• Otherwise, split the tree at the middle level into a "top tree" of the first half of the nodes and up to $\sqrt{n}$ "bottom trees" formed from the lower levels. Recursively compute the van Emde Boas layouts of each of these trees, then concatenate them together in order.

You can prove that this layout is optimal assuming that you don't know anything about the particular sizes of the caches of the machines in the computer (it's known as a cache-oblivious data structure).

If you do know the cache size, though, the "best" choice is probably to use a B-tree instead of a BST, since B-trees are specifically designed to play nicely with caches. Although they were designed for on-disk storage, they work really well in main memory, as some recent work has shown.

Answer 3

I might be confused as I usually see DFS or BFS in connection with tree traversing, as opposed to binary searching. You mean to store tree items sequentially in an array in the traversed order, I guess...

But what I think you are after are cache-oblivious algorithms (also here and here). There are many links I could post here but instead you could try to search for "cache oblivious {tree, btree, layout, heap, search, ...}". Especially interesting is so-called "van Emde Boas layout" which makes the optimal number of memory transfers.

Also try to look at D-heap and B-heap, even if they are not exactly binary search related.