Ordering Using Stern-Brocot Trees

While developing for Mythic, I was updating the page ordering from a plain, static alphabetical sort to a user-defined custom ordering. At first blush this would seem to be a fairly straight-forward problem to solve. Slap an order number column onto the database and you’re done. However, to avoid performance bottlenecks and data type issues, it ended up being a little more complicated than that. Here’s how I used a Stern-Brocot tree to implement an easy to use custom page ordering feature.

First, let’s look at the problem space a little more. There are several different options to choose from when it comes to selecting an ordering method.

Integers

What’s wrong with just using integers? In Mythic if you have 100 pages, why not just order them with the first in the navigation at 1, and the last at 100, and sort ascending? Easy and understandable.

But if we move page 25 to the 75th slot, what do we do with all the pages above or below it? We would need to change the order number of all 50 pages in between, or increment the order of all pages above 75 and leave a gap at 25.

Updating 50 different pages, just to move a single page is not an efficient way to keep the database in sync.

Additionally, page ordering is implemented using a drag and drop interface, making it a very simple mechanism for someone to use frequently, causing a lot of update requests to the database. Each of those requests could require updating nearly every database row for the pages in the Storybook.

Decimals and floating-points

Okay, well instead of whole numbers, why don’t we look at fractions? Then we can slot a page between two numbers. In our previous example, we could set the page order of the moved page to 74.5. Now we only need to update a single database row. Much better!

But it won’t take long before things start getting pretty dicey with those floating-point numbers. As pages get moved around, soon you have 74.25, 74.125, 74.0625, 74.03125 and so on. Floating-point precision storage can be a hassle, and as a bonus, floating-point arithmetic is error-prone.

Strings

Okay, maybe rather than dealing with integer issues and floating-point storage, we can look at text strings. This is simple to store in the database. Sorting A-Z is just as simple as 1-100, but how to handle more than 26 items? Duplicate letters? A, AA, AAA? But how do you get a page to order between A and AA? You can “increment” the final letter of the later page first. So AA becomes AB. Then the order of the page being moved is set to AA. When another page slots in you get AC and AB (or AAA?) This gets difficult to reason about and hard to read very quickly.

Stern-Brocot

Alright, enough unused options, let's get down to a solution.

A Stern-Brocot tree is a hierarchy of numbers written as fractions where every number is (exclusively) between `0/1` and the irrational `1/0`, with the root node starting at `1/1`. Every new node is created between neighbouring nodes. This is done by separately adding the numerators and denominators of those two numbers: `(N_1+N_2)/(D_1+D_2)`.

From the root node, combining `1/1` and `0/1` gives us `(1+0)/(1+1) = 1/2` while combining `1/1` and `1/0` is `(1+1)/(1+0) = 2/1` (or 2). To create a node between `1/2` and `1/1`, we again combine those together giving us `(1+1)/(2+1) = 2/3`. Between `1/1` and `2/1`, it’s `(1+2)/(1+1) = 3/2`. The Wikipedia article has a diagram and further mathematical explanations which may be helpful.

The tree is generally used to design gear ratios, but because it can be infinitely expanded we can use it to sort our pages using the same concept as the floating-point numbers. The difference here is we are writing them as fractions to avoid the aforementioned issues and, this is the important part, storing them as text strings in their fraction form.

Though the fractions are stored as strings, even unwieldy large fractions will only be 10s of bytes long.

The Frontend

Since Mythic stores all pages across users in the same table, it doesn't make much sense to keep everything ordered in the database. That's why fractions stored as text work. We don’t need a data format that can be sorted by the database, but by the code once the data is retrieved.

To order pages, we need to first convert the text to numbers. Taking the fraction `2/3`, 2/3 in normal text form, we split on the / to get 2 and 3. While we could create floating-point number from here, using whole numbers means never worrying about rounding errors or other inherent issues. To compare the fractions as whole numbers, multiply the numerator of one by the denominator of the other (for both sets) and compare those numbers.

Let's use `2/3` and `5/4` as an example. Doing the multiplication gives us 8 and 15: `2*4 < 3*5 => 8 < 15`. This is trivial for the computer to order. Additionally, the fraction notation is simpler for humans to order than two similar floating-point numbers 16 decimals long.

For inserting new items, or moving an item around, we just need to get the fractions of the preceding and succeeding items and find the mediant fraction between the two, using the formula above. The entire list is not recalculated, so if a new page is placed where an old one was move away from, it will simply re-use the old fraction. This helps keep the tree depth from spiralling.

So far this method has worked without issue. I hope this was a useful explaination and helped if you were searching for ways to sort!