Хранить упорядоченный список в базе данных (подход с пропуском) - PullRequest
Новая
       1

Хранить упорядоченный список в базе данных (подход с пропуском)

8 голосов
/ 13 апреля 2011

Я хочу сохранить большой упорядоченный список (миллионы элементов) в хранилище данных Google App Engine.Требуется быстрая вставка.

Самый простой способ - добавить индексированное свойство (или столбец) "order_num", представляющее порядок.Например, список [A, B, C] будет храниться так: 

content   order_num
--------------------
   A         1
   B         2
   C         3

Однако это не дает вам быстрой вставки.Например, если я хочу вставить X после A, мне нужно изменить нумерацию B и C, чтобы «освободить место» для X, т. Е. Пусть B станет 3, C станет 4, а X будет 2. Это было бы катастрофой, если бы яимеют миллионы элементов.

Я нашел выполнимое решение, названное "подход с разрывом", описанное здесь .Этот подход сохраняет разрыв между смежными элементами.Например: 

content   order_num
--------------------
   A         1000
   B         2000
   C         3000

Когда я хочу вставить X после A, я могу просто добавить X с его порядковым номером (1000 + 2000) / 2 = 1500, перенумерация не требуется.

Но с уменьшением этих пробелов может потребоваться перенумерация.У меня вопрос, есть ли известная стратегия по нумерации?И решить размер пробелов?

Спасибо!

ОБНОВЛЕНИЕ

Вот более подробно.Скажем, у меня есть список элементов в базе данных, и каждый элемент имеет целочисленное свойство с именем my_num.Значение my_num - произвольное положительное целое число.Предположим, у меня есть список [A, B, C, D], и их my_num 

 element    my_num   
---------------------
   A          5        
   B          2
   C         10
   D          7

Теперь давайте определим оператор мог (): 

accum(n) = element[0].my_num + element[1].my_num + ... + element[n-1].my_num

Итак, накопзначения для каждого элемента: 

 element    my_num   accum 
----------------------------
   A          5        5
   B          2        7
   C         10       17
   D          7       24

Но накопленные значения, вероятно, НЕ должны храниться в базе данных, поскольку список постоянно обновляется.Лучше быстро вставлять.

Я хочу создать запрос, в качестве входного значения которого используется целое число x: 

query(x) = element[i] if accum(i-1) < x <= accum(i)

Например, query (11) - это C, а query (3) -A.

Можно ли спроектировать схему хранилища данных, чтобы сделать этот запрос быстрым?Или единственный способ накапливать его один за другим во время запроса, что я планирую сделать?

Ответы [ 3 ]

11 голосов
/ 13 апреля 2011

альтернативно, вы могли бы использовать десятичные дроби или строку? 

content     order
-------------------- 
   A         'a' 
   B         'b' 
   C         'c'

Затем, чтобы вставить D между a и b, присвойте ему значение 'aa'

Алгоритм генерации строк лучше всего показан для двоичной строки: если вы хотите вставить что-то между «1011» и «1100», выполните следующее:

  • Avalue = 1 + 0 * (1/2) + 1 * (1/4) + 1 * (1/8)
  • Bvalue = 1 + 1 * (1/2) + 0 * (1/4) + 0 * (1/ 8)

среднее, новое значение = 1 + 0 * (1/2) + 1 * (1/4) + 1 * (1/8) + 1 * (1/16)new string = "10111" 

content     order
-------------------- 
   A         '1011' 
   new!      '10111' 
   B         '1100' 
   C         '1101'

, поскольку вы всегда усредняете 2 значения, среднее всегда будет иметь конечное двоичное развитие и конечную строку.Он эффективно определяет бинарное дерево.

Как вы знаете, бинарные деревья не всегда оказываются хорошо сбалансированными, другими словами, некоторые строки будут намного длиннее других после достаточного количества вставок.Чтобы они были короткими, вы можете использовать любую четную числовую базу - она ​​должна быть четной, потому что тогда разработка любого среднего из двух значений будет конечной.

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

2 голосов
/ 14 апреля 2011

Возможно, вы захотите использовать app-engine-ranklist , который использует древовидную структуру для поддержания порядка рангов в хранилище данных.

Или, если вы можете описать ваши требования более подробно, возможно, мы можем предложить альтернативу, которая включает в себя меньше накладных расходов.

1 голос
/ 13 апреля 2011

Вы можете создать гигантский связанный список ...., где каждая сущность будет указывать на следующую в списке.

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

В базе данных ваш связанный список можно сделать так: 

value (PK)   predecessor
------------------------
  A              null
  B               A
  C               B

затем при вставке новых данных измените предшественник: 

value (PK)   predecessor
------------------------
  A              null
  B               A
  C               D
  D               B

Вставка выполняется быстро, но перемещение будет действительно медленным!

...