Let me ask you a quick question: how would you design a system if your application required data to be arranged in any arbitrary order? There are several approaches to this.
In a project I participated in, we originally used the acts_as_list gem to manage the position of items with incremental integers. Every time the position of items was changed, the client would send all the reordered data to the server, which then recalculated the positions.
While this approach worked for small datasets with fewer than 10 items, as the data size increased, the performance slowed down significantly. This led to the need to recalculate the positions of up to N items, raising questions about the efficiency of this approach. It was this performance issue that prompted me to explore a more efficient way to manage positions and eventually led to the development of this gem.
Fractional Indexing
The ideal solution I envisioned was one where only the repositioned data (N=1) needs recalculating. While searching for such a solution, I came across the "Fractional Indexing" method. This method represents positions not only with integers but also using decimal points.
With Fractional Indexing, when you move an item between two others, the new position is calculated as the average value between the positions of those two items. This way, only the repositioned data requires recalculation.
This approach seemed perfect for my needs, but there were some significant limitations.
The Limitations of Traditional Fractional Indexing
One major problem is that as the data is reordered repeatedly, the number of digits increases, and fairly quickly, rounding errors can cause multiple items to have the same position. In addition, when positions duplicate, a relatively heavy rebalancing operation (reassigning the position for all items) becomes necessary.
Figma's Approach to Fractional Indexing
After reading Figma's blog post, I realized that their approach had two key advantages that could solve the problems of traditional Fractional Indexing:
- Using strings to represent positions, which not only relaxes the limitations on the number of digits but also eliminates concerns about rounding errors causing collisions in the position values.
- By representing the position as a string, base-95 numbering can be used instead of base-10, which means rebalancing is generally unnecessary.
Based on these insights, I created a new gem that provides an efficient mechanism for managing positions using this approach. This gem allows for more efficient sorting operations.
Introducing the Gem fractional_indexer
As mentioned in the README, this gem is based on Implementing Fractional Indexing, with a few tweaks. It provides an algorithm that implements the approach introduced in Figma’s blog post.
Understanding the Generated Values
NOTE: In the following explanation of the gem’s internal implementation, I will use base-10 numbering (characters 0 through 9) instead of the default base-62 for simplicity.
The strings representing the position generated by this gem consist of three parts, as shown below:
Let’s start with the prefix. The prefix, represented by lowercase letters (a–z) and uppercase letters (A–Z), serves two main purposes:
- It indicates how many digits make up the integer part of the value (i.e., how many characters represent the integer portion).
- It distinguishes between positive and negative integers.
| Value/Number of Digits | 1 | 2 | 3 | 4 | 5 | ... | 26 |
|---|---|---|---|---|---|---|---|
| Positive Integer | a | b | c | d | e | ... | z |
| Negative Integer | Z | Y | W | X | Y | ... | A |
This table illustrates how the prefix represents the number of digits and whether the value is positive or negative. For example, a prefix of a indicates a one-digit positive integer, while b indicates a two-digit positive integer. Similarly, Z indicates a one-digit negative integer, and Y indicates a two-digit negative integer. This system ensures that the order is preserved mathematically, regardless of the string’s length.
The next part is the integer value, which corresponds to the number of characters specified by the prefix.
Finally, the decimal part refers to the remaining characters after the prefix and the integer value.
There’s one important rule for the decimal part: the last character must not be the smallest value in the numbering system. This rule exists to ensure that values like 1.20 and 1.2 are treated as equivalent. Therefore, the trailing 0 is explicitly omitted for consistency.
Behavior During Reordering
As mentioned earlier when discussing Fractional Indexing, "the average value between two elements is used as the new order when moving an item." This approach generally leads to an exponential increase in the number of digits (or characters) with each reorder.
However, this gem is designed to minimize the increase in digits as much as possible. The benefit of preventing the increase in digits is that it helps reduce the size of the index when persisting the order in a database, making it easier to manage fields like VARCHAR in SQL.
The diagram below illustrates how the order is assigned when items are reordered.
Integrating with Active Record: Introducing Gem narabikae
Building on the fractional_indexer described above, I developed the gem narabikae, which integrates with Active Record to provide a simple and familiar interface for automatically generating and managing order, similar to acts_as_list.
This gem offers the following features with a simple syntax:
✅ Automatic order generation and persistence when creating records
✅ Several methods for reordering records
✅ Support for scoping
✅ Retry mechanism for handling order collisions
This gem provides a simple yet powerful tool for managing and reordering items efficiently. I encourage you to try it out in your project and experience the improved performance and ease of use for yourself. I would love to hear your feedback!
Top comments (0)