motoko-base icon indicating copy to clipboard operation
motoko-base copied to clipboard

Add `entriesTail` method to `RBTree`

Open jzxchiang1 opened this issue 2 years ago • 5 comments

Inspired by Java's TreeMap#tailMap method but this one automatically gives you an iterator.

The use case is cursor pagination through a long list.

I've been trying to implement cursor pagination in the IC. Think a long list of items that a client needs to fetch, e.g. comments on a post, stories on a feed, etc. The client should fetch a small number of items at a time, say 20, in order to minimize server load as well as meet IC message requirements (<2 MB for requests, I think).

Offset pagination is one option, but it's not really viable at all for real-time, dynamic data. If items get removed or added while the user is scrolling through a partial list, it can result in skipped or duplicate data rendered on the client. At least there isn't really a performance hit on the IC, since it can be implemented with array indexing thanks to orthogonal persistence.

As a result, cursor pagination is generally preferred. In web2 land, this is generally done with a SQL query WHERE id > ... LIMIT .... This requires id be sorted in some database index. On the IC, the only data structure that can emulate a sorted map like this is RBTree.

So in this PR, I add a new method to the RBTree.RBTree class that allows a user to pass in some cursor (i.e. x) to continue iterating where they left off, crucially in ~O(log n) time.

jzxchiang1 avatar Dec 23 '21 09:12 jzxchiang1