Произвольно упорядочивая записи в таблице

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

Общее решение, которое я видел, состоит в том, чтобы добавить целочисленный столбец order:

CREATE TABLE AS your_table (id, title, sort_order)
AS VALUES
  (0, 'Lorem ipsum',   3),
  (1, 'Dolor sit',     2),
  (2, 'Amet, consect', 0),
  (3, 'Elit fusce',    1);

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

Однако это кажется неуклюжим

• Если я хочу переместить запись 0 в начало, я должен изменить порядок каждой записи
• Если я хочу вставить новую запись в середине, я должен изменить порядок каждой записи после нее
• Если я хочу удалить запись, я должен изменить порядок каждой записи после нее

Легко представить такие ситуации, как:

• Две записи имеют одинаковые order
• orderМежду записями есть пробелы

Это может произойти довольно легко по ряду причин.

Такой подход используют такие приложения, как Joomla:

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

Некоторые люди предлагают использовать десятичную для сохранения порядка, так что вы можете использовать «2.5» для вставки записи между записями в порядке 2 и 3. И хотя это немного помогает, возможно, это даже более грязно, потому что вы можете в конечном итоге с странные десятичные дроби (где вы остановитесь? 2,75? 2,875? 2,8125?)

Есть ли лучший способ хранить заказ в таблице?

Если я хочу переместить запись 0 в начало, я должен изменить порядок каждой записи

Нет, есть более простой способ.

update your_table
set order = -1 
where id = 0;

Если я хочу вставить новую запись в середине, я должен изменить порядок каждой записи после нее

Это правда, если только вы не используете тип данных, который поддерживает значения «между». Числа с плавающей точкой и числовые типы позволяют обновить значение, скажем, до 2,5. Но varchar (n) тоже работает. (Думайте 'a', 'b', 'c'; затем думайте 'ba', 'bb', 'bc'.)

Если я хочу удалить запись, я должен изменить порядок каждой записи после нее

Нет, есть более простой способ. Просто удалите строку. Остальные строки все равно будут отсортированы правильно.

Легко представить такие ситуации, как:

Две записи имеют одинаковый порядок

Уникальное ограничение может предотвратить это.

Между записями есть пробелы

Пробелы не влияют на то, как dbms сортирует значения в столбце.

Некоторые люди предлагают использовать десятичную для сохранения порядка, так что вы можете использовать «2.5» для вставки записи между записями в порядке 2 и 3. И хотя это немного помогает, возможно, это даже более грязно, потому что вы можете в конечном итоге с странные десятичные дроби (где вы остановитесь? 2,75? 2,875? 2,8125?)

Вы не остановитесь, пока не должны . У DBM нет проблем с сортировкой значений, которые имеют 2, 7 или 15 знаков после запятой.

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

create table your_table (
  id int primary key, 
  title varchar(13), 
  sort_order float
);

insert into your_table values
(0, 'Lorem ipsum', 2.0),
(1, 'Dolor sit', 1.5),
(2, 'Amet, consect', 0.0),
(3, 'Elit fusce', 1.0);

-- This windowing function will "transform" the floats into sorted integers.
select id, title,
       row_number() over (order by sort_order)
from your_table

Это очень просто. Вы должны иметь структуру "кардинальной дыры":

Вам нужно иметь 2 столбца:

1. рк = 32 бит integer
2. заказ = 64 бит bigint( не double )

Вставка / обновление

1. При вставке первой новой записи установите order = round(max_bigint / 2).
2. При вставке в начале таблицы установите order = round("order of first record" / 2)
3. При вставке в конце таблицы установите order = round("max_bigint - order of last record" / 2) 4) При вставке в середине установитеorder = round("order of record before - order of record after" / 2)

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

В максимальной ситуации с нормализацией (с этой структурой) вы можете иметь «дыру в кардинальности» в 32 битах.

Помните, что не следует использовать типы с плавающей точкой - порядок должен быть точным значением!

Как правило, упорядочение производится в соответствии с некоторой информацией в записях, заголовком, идентификатором или чем-либо, что подходит для данной конкретной ситуации.

Если вам нужен специальный порядок, использование целочисленного столбца не так плохо, как может показаться. Например, чтобы освободить место для записи на 5-м месте, вы можете сделать что-то вроде:

update table_1 set place = place + 1 where place > 5,

Надеюсь, вы можете объявить столбец uniqueи, возможно, иметь процедуру, чтобы сделать перестановки «атомарными». Детали зависят от системы, но это общая идея.

... возможно, это даже более грязно, потому что вы можете получить странные десятичные дроби (где вы остановитесь? 2.75? 2.875? 2.8125?)

Какая разница? Эти цифры предназначены только для компьютера, поэтому не имеет значения, сколько у них дробных цифр или насколько они уродливы.

Использование десятичных значений означает, что для перемещения элемента F между элементами J и K все, что вам нужно сделать, это выбрать значения порядка для J и K, затем усреднить их, а затем обновить F. Два оператора SELECT и один оператор UPDATE (вероятно, это делается с использованием сериализуемой изоляции, чтобы избежать тупики).

Если вы хотите видеть целые числа, а не дроби в выходных данных, то либо рассчитайте целые числа в клиентском приложении, либо используйте функции ROW_NUMBER () или RANK () (если ваша СУБД включает их).

В моем собственном проекте я планирую попробовать решение, подобное решению с десятичным числом, но вместо этого использовать байтовые массивы:

def pad(x, x_len, length):
    if x_len >= length:
        return x
    else:
        for _ in range(length - x_len):
            x += b"\x00"
        return x

def order_index(_from, _to, count, length=None):
    assert _from != _to
    assert _from < _to

    if not length:
        from_len = len(_from)
        to_len = len(_to)
        length = max(from_len, to_len)

        _from = pad(_from, from_len, length)
        _to = pad(_to, to_len, length)

    from_int = int.from_bytes(_from, "big")
    to_int = int.from_bytes(_to, "big")
    inc = (to_int - from_int)//(count + 1)
    if not inc:
        length += 1
        _from += b"\x00"
        _to += b"\x00"
        return order_index(_from, _to, count, length)

    return (int.to_bytes(from_int + ((x+1)*inc), length, "big") for x in range(count))

>>> index = order_index(b"A", b"Z", 24)
>>> [x for x in index]
[b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X', b'Y']
>>> 
>>> index = order_index(b"A", b"Z", 25)
>>> [x for x in index]
[b'A\xf6', b'B\xec', b'C\xe2', b'D\xd8', b'E\xce', b'F\xc4', b'G\xba', b'H\xb0', b'I\xa6', b'J\x9c', b'K\x92', b'L\x88', b'M~', b'Nt', b'Oj', b'P`', b'QV', b'RL', b'SB', b'T8', b'U.', b'V$', b'W\x1a', b'X\x10', b'Y\x06']

Идея состоит в том, что вы никогда не можете исчерпать возможные промежуточные значения, потому что вы просто добавляете a b"\x00"к соответствующим записям, если вам нужно больше значений. ( intне ограничен в Python 3, в противном случае вам придется выбирать срез байтов в конце для сравнения, при условии, что между двумя смежными значениями различия будут упакованы ближе к концу.)

Например, скажем, у вас есть две записи, b"\x00"и b"\x01", и вы хотите, чтобы запись проходила между ними. Там нет никаких доступных значений между 0x00и 0x01, таким образом вы добавите b"\x00"к обеим, и теперь у вас есть несколько значений между ними вы можете использовать для вставки новых значений.

>>> records = [b"\x00", b"\x01", b"\x02"]
>>> values = [x for x in order_index(records[0], records[1], 3)]
>>> records = records + values
>>> records.sort()
>>> records
[b'\x00', b'\x00@', b'\x00\x80', b'\x00\xc0', b'\x01', b'\x02']

База данных может легко сортировать это, потому что все заканчивается в лексикографическом порядке. Если вы удалите запись, она все еще в порядке. В моем проекте я сделал b"\x00"и b"\xff"как FIRSTи LASTзаписи, однако, чтобы использовать их как виртуальные значения «от» и «до» для добавления / добавления новых записей:

>>> records = []
>>> value = next(order_index(FIRST, LAST, 1))
>>> value
b'\x7f'
>>> records.append(value)
>>> value = next(order_index(records[0], LAST, 1))
>>> value
b'\xbf'
>>> records.append(value)
>>> records.sort()
>>> records
[b'\x7f', b'\xbf']
>>> value = next(order_index(FIRST, records[0], 1))
>>> value
b'?'
>>> records.append(value)
>>> records.sort()
>>> records
[b'?', b'\x7f', b'\xbf']

Я нашел этот ответ намного лучше. Цитирую это целиком:

Базы данных оптимизированы для определенных вещей. Быстрое обновление большого количества строк является одним из них. Это становится особенно актуальным, когда вы позволяете базе данных выполнять свою работу.

Рассмотреть возможность:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

И вы хотите перейти Beat Itк концу, у вас будет два запроса:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

Вот и все. Это очень хорошо масштабируется с очень большими числами. Попробуйте поместить несколько тысяч песен в гипотетический плейлист в вашей базе данных и посмотрите, сколько времени потребуется для перемещения песни из одного места в другое. Поскольку они имеют очень стандартизированные формы:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

У вас есть два подготовленных заявления, которые вы можете использовать очень эффективно.

Это дает некоторые существенные преимущества - порядок таблиц можно обдумать. Третья песня имеет order3, всегда. Единственный способ гарантировать это - использовать последовательные целые числа в качестве порядка. Использование псевдосвязанных списков или десятичных чисел или целых чисел с пробелами не позволит вам гарантировать это свойство; в этих случаях единственный способ получить n-ю песню - это отсортировать всю таблицу и получить n-ную запись.

И действительно, это намного проще, чем вы думаете. Просто выяснить, что вы хотите сделать, сгенерировать два оператора обновления, а другим людям посмотреть на эти два оператора обновления и понять, что делается.