Концепция устойчивого к репликации sortKey

Я ищу материал, раскрывающий эту идею:

Учитывая структуру данных в виде списка (например, таблицу базы данных), следует ввести свойство (столбец) sortKey, которое

  1. отражает желаемый порядок сортировки (ORDER BY sortKey)
  2. уникален в списке
  3. делает возможными вставки в любую позицию в (отсортированном) списке
  4. неизменен

Требования 1-3 могут быть выполнены с помощью целочисленного sortKey, где при каждой вставке всем элементам потенциально назначается новый sortKey.

Требования 1-4 могут быть выполнены с помощью ключа сортировки древовидный, например диапазон десятичного типа (0,0, 1,0); каждая вставка будет читать sortKey для своего предшественника и преемника и использовать sortKey (newItem) = (sortKey (слева) + sortKey (справа)) / 2

Есть ли общий термин для этой проблемы / решения, который я могу найти, или кто-нибудь может указать мне на literatur.

Спасибо!

ReactJs | Supabase | Добавление данных в базу данных
ReactJs | Supabase | Добавление данных в базу данных
Это и есть ваш редактор таблиц в supabase.👇
1
0
31
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

На самом деле не существует хорошего решения, отвечающего всем этим требованиям. (3) + (4) требует, чтобы ключи были переменной длины, и злоумышленник всегда может найти последовательность вставки, которая делает длину ключей пропорциональной количеству вставленных ключей.

Эта проблема называется "проблемой маркировки онлайн-списков" или "проблемой обслуживания заказа", и поиск в Google по этим терминам обнаружит различные компромиссы, которые могут быть вам полезны, а могут и не оказаться.

https://en.wikipedia.org/wiki/Order-main maintenance_problem

Другие вопросы по теме