# David Greenspan - Implementing Fractional Indexing (Highlights)  ## Metadata **Review**:: [readwise.io](https://readwise.io/bookreview/61531602) **Source**:: #from/readwise #from/reader **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[David Greenspan]] **Full Title**:: Implementing Fractional Indexing **Category**:: #articles #readwise/articles **Category Icon**:: 📰 **URL**:: [readwise.io](https://readwise.io/reader/document_raw_content/468346518) **Host**:: [[readwise.io]] **Highlighted**:: [[2026-06-22]] **Created**:: [[2026-07-04]] ## Note <https://observablehq.com/@dgreensp/implementing-fractional-indexing> ## Highlights - We can represent the digits of a decimal as a string, so instead of 0.5, it's "5". When we switch from numbers to strings, the natural order we are taking advantage of is lexicographical order rather than numeric order. ([View Highlight](https://read.readwise.io/read/01kvpbdfctdaea6tb8pfg0bnkk)) ^1027549445 - To represent one, we can use a sentinel value such as END or null. ([View Highlight](https://read.readwise.io/read/01kvpben75pxahwjjpsjp2bjs8)) ^1027549502 - say that "3" and "30" are distinct order keys, but the problem is there are no other digit strings that sort between them ([View Highlight](https://read.readwise.io/read/01kvpbdxb1sqqbfchqn6zzp1y7)) ^1027549468 - One property we'd like our midpoint algorithm to have is it doesn't needlessly grow the number of digits. ([View Highlight](https://read.readwise.io/read/01kvpbgg5a6fj8hhb3hst8xmja)) ^1027549576 - When �nding the longest common pre�x, we must treat A as if it is followed by as many trailing zeros as we need to match zeros in B. For example, "123" and "123004" have a common pre�x of "12300". ([View Highlight](https://read.readwise.io/read/01kvpbjsdqd9qb4pkt50x2vkj5)) ^1027549653 - For the purposes of the following steps, if A is empty, we'll say the �rst digit is 0. If B is null, we'll say its �rst digit is 10 (an imaginary digit one larger than 9). ([View Highlight](https://read.readwise.io/read/01kvpbkpq5z3xh868wczb4cnsz)) ^1027549688 - We could give list items keys like 1, 2, and 3, and only if you insert or move an item between these keys, create keys like 0.5, 1.5, and 2.5. When �nding a "midpoint" between a key and END, we would always choose the smallest integer that is larger than the key. These integer keys would accumulate bits at a logarithmic rate as we increment them. ([View Highlight](https://read.readwise.io/read/01kvpbt81w4twkpb1skw2m6ns4)) ^1027550028 - To support both prepending and appending to the list without going into the fractional part, we could start in the middle of the integers, with the �rst list item getting key "5000000000". ([View Highlight](https://read.readwise.io/read/01kvpbvzhnhk2cxxctprfen96z)) ^1027550099 - However, with base 95, ten digits gives us a little more than 65 bits of integer precision, which is many billions of billions of items. ([View Highlight](https://read.readwise.io/read/01kvpbvnyz5yn5kzbe5wmft24q)) ^1027550092 - For example, 1 to 9 could be written A1 to A9, while 10 to 99 are written B10 to B99. In fact, we might as well use A0 to A9 and B00 to B99. ([View Highlight](https://read.readwise.io/read/01kvpbx3hgf03jsbe8rqsthhsm)) ^1027550142