我在一个集合中有一系列"行"，这些行被持久化到nosql数据库(在本例中为Firestore(。我的每一行都有一个排序顺序，这是在用户添加、插入、复制或移动集合中的行时建立的。用户可以插入新记录的插入点是任意的。排序顺序被持久化到后端，并且可以按排序顺序字段进行检索。集合中可能有大量的行，数量为50K。
问题是什么样的排序顺序编码格式可以允许在现有记录之间重复插入新记录，而不必偶尔重写整个集合的排序索引，以在相邻记录之间的排序顺序中提供"空间"。
我猜可能有一些标准的方法来实现这一点，但不确定它是什么
假设字母表是"abc"。然后：
b、 c，cb。。。
是一个按字典排序的列表，允许您在任何位置插入项目：
ab、b、bb、c、cab、cb、cbb。。。
结果仍然是一个列表，可以在任何地方插入项目：
aab，ab，ac，b，bab，bb，bc，c，caab，cab，cac，cb，cbb，cbb。。。
诀窍是避免将"a"作为项目的最后一个字符，这样您就可以始终将项目放在其他项目之后
使用64个ASCII字符而不是3个字符执行此操作。
我已经考虑了好几个月了。这是我到目前为止在实现它方面的进展。它仍然有一些缺陷，有点乱，但我想我会清理它，并在我有更多时间的时候上传到npm。
// Originally written in TypeScript, then removed the types for SO.
const alphabet = 'abc';
function getHigherAsciiChar(char) {
const index = alphabet.indexOf(char);
if (index === alphabet.length - 1) {
return ''; // sorry, there's no higher character
}
const nextIndex = Math.ceil((index + alphabet.length - 1) / 2);
return alphabet.charAt(nextIndex);
}
function getCharBetween(minChar, maxChar) {
if (minChar > maxChar) {
throw new Error('minChar > maxChar, ' + minChar + ' > ' + maxChar);
}
const minIndex = alphabet.indexOf(minChar);
const maxIndex = alphabet.indexOf(maxChar);
const nextIndex = Math.floor((minIndex + maxIndex) / 2);
if (nextIndex === minIndex) {
return ''; // there is no character between these two
}
return alphabet.charAt(nextIndex);
}
function getPaddedString(finalLength, string) {
let result = string;
while (result.length < finalLength) {
result += alphabet.charAt(0);
}
return result;
}
function getOrderString(bounds) {
const console = { log: () => {} }; // uncomment this to log debug stuff
if (!bounds.previous && !bounds.next) {
return getHigherAsciiChar(alphabet[0]);
}
const previousString = bounds.previous || '';
if (!bounds.next) {
const firstPreviousChars = previousString.substr(0, previousString.length - 1);
const lastPreviousChar = previousString.charAt(previousString.length - 1);
return firstPreviousChars + (
getHigherAsciiChar(lastPreviousChar) || (
lastPreviousChar + getHigherAsciiChar(alphabet.charAt(0))
)
);
}
const nextString = bounds.next;
console.log(`Searching between '${previousString}' and '${nextString}'...`);
const bigStringLength = Math.max(previousString.length, nextString.length);
const previous = getPaddedString(bigStringLength, previousString);
const next = getPaddedString(bigStringLength, nextString);
console.log(previous, next);
let result = '';
let i;
for (i = 0; i < bigStringLength; i++) {
const previousChar = previous.charAt(i);
const nextChar = next.charAt(i);
// keep adding common characters
if (previousChar === nextChar) {
result += previousChar;
console.log(result, 'common character');
continue;
}
// when different characters are reached, try to add a character between these two
const charBetween = getCharBetween(previousChar, nextChar);
if (charBetween) {
result += charBetween;
console.log(result, 'character in-between. RETURNING');
// and you're done
return result;
}
// if there was no character between these two (their distance was exactly 1),
// repeat the low character, forget about the upper bound and just try to get bigger than lower bound
result += previousChar;
console.log(result, 'the lower character so we can forget about high bound');
i++;
break;
}
for (; previousString >= result; i++) {
const previousChar = previous.charAt(i);
const higherChar = getHigherAsciiChar(previousChar);
if (higherChar) {
// you found a digit that makes your result greater than the lower bound. You're done.
result += higherChar;
console.log(result, 'a higher character. RETURING');
return result;
}
// the digits are still very close, can't find a digit in-between (yet)
result += previousChar;
console.log(result, 'moving on to next digit');
}
// so you end up depleting all the character slots from the lower bound. Meh, just add any character.
result += getHigherAsciiChar(alphabet.charAt(0));
console.log(result, 'meh, just add any character. RETURNING');
return result;
}
function interleaveTest(order) {
const newOrder = [];
newOrder.push(getOrderString({ next: order[0] }));
for (let i = 0; i < order.length - 1; i++) {
newOrder.push(order[i]);
newOrder.push(getOrderString({ previous: order[i], next: order[i + 1] }));
}
newOrder.push(order[order.length - 1]);
newOrder.push(getOrderString({ previous: order[order.length - 1] }));
return newOrder;
}
let order = ['c'];
console.log('n' + order.join(', ') + 'n');
order = interleaveTest(order);
console.log('n' + order.join(', ') + 'n');
order = interleaveTest(order);
console.log('n' + order.join(', ') + 'n');
order = interleaveTest(order);
console.log('n' + order.join(', ') + 'n');
let atEnd = ['b'];
for (let i = 0; i < 10; i++) {
atEnd.push(getOrderString({ previous: atEnd[atEnd.length - 1] }));
}
console.log('nat end: ' + atEnd.join(', ') + 'n');