Sample for how to save a sorted list in a database

In my previous blog, I wrote about common approaches how to save a sorted list in a database. I didn’t find an implementation of the hybrid approach and as it’s very simple I’ll share an isolated version here. I’ll extract also an interface, so you can easily plug your database, as I’m using Cosmos DB and you may use something else.

A big benefit of this approach there is no need of scheduled re-indexing.

You can find the code here:

The usage is simple. All you need to do is implement IDatabase (That’s to connect to your database) and IIndexedItem (The model of the item that you want to save in ordered list)

The whole “magic” is happening in this part of the code.

private async Task InsertInTheMiddle(TItem item, TItem previousItem, TItem nextItem)
{
	decimal increase = (nextItem.Index - previousItem.Index) / IndexGapDivider;

	if (increase < IndexInitiateReindex)
	{
		await ReindexItemsAsync(previousItem);
		increase = (nextItem.Index - previousItem.Index) / IndexGapDivider;
		item.Index = previousItem.Index + increase;
	}
	else
	{
		item.Index = previousItem.Index + increase;
	}
	previousItem.NextId = item.Id;
	await Database.UpdateAsync(previousItem);
}		

protected virtual async Task ReindexItemsAsync(TItem previousItem)
{
	var item = previousItem;
	var index = item.Index;

	var asyncTasks = new List<Task>();
	while (item != null && item.Index >= index - IndexReindexStep)
	{
		index -= IndexReindexStep;
		item.Index = index;
		asyncTasks.Add(Database.UpdateAsync(item));
		item = await GetPreviousItemAsync(item.Id);
	}
	Task.WaitAll(asyncTasks.ToArray());
}

Basically, I detect if there is a place to insert and if there is not – re-index the previous items to increase the gap.

Based on what’s the pattern of the inserts you can adjust these values to decrease the chance of required re-indexes.

protected decimal IndexGapSize = 64;
protected decimal IndexInitiateReindex = 0.0000001M;
protected decimal IndexReindexStep = 0.00001M;
protected decimal IndexGapDivider = 2;

Worst scenario – You always insert at the same spot somewhere in the middle. In this case, the gap will deplete very fast. If that’s your case you can consider overwriting the logic of re-indexing to distribute the space not evenly but leave a bigger gap in the second half
An example you can see in TestOrderedListWorstCase where I’m dealing with the case where we always insert at the same spot.

In the code, you can find a simple example and unit tests.

Nice compliment for such a method is to use a database cache, so you don’t block your application while the re-indexing is happening. I’ll write a blog post about how you can achieve that easily.

In my use case, I have a hierarchical structure which I didn’t include here, to keep it simple. Let me know if your case also needs hierarchy and I’ll add more information about that