it-swarm-eu.dev

Libovolné řazení záznamů v tabulce

Běžnou potřebou při používání databáze je přístup k záznamům v pořádku. Například, pokud mám blog, chci mít možnost uspořádat své blogové příspěvky v libovolném pořadí. Tyto položky často mají spoustu vztahů, takže relační databáze má smysl.

Běžné řešení, které jsem viděl, je přidání celého sloupce 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);

Pak můžeme řadit řádky podle order, abychom je dostali ve správném pořadí.

Zdá se však, že je to nemotorné:

  • Pokud chci přesunout záznam 0 na začátek, musím změnit pořadí každého záznamu
  • Pokud chci vložit nový záznam uprostřed, musím po každém záznamu změnit pořadí každého záznamu
  • Pokud chci odstranit záznam, musím po každém záznamu změnit pořadí všech záznamů

Je snadné si představit situace jako:

  • Dva záznamy mají stejné order
  • V záznamech order jsou mezery

To se může stát docela snadno z několika důvodů.

Toto je přístup, který používají aplikace jako Joomla:

Example of Joomla's approach to ordering

Dalo by se tvrdit, že rozhraní je zde špatné a že místo přímého editování čísel by měli používat šipky nebo přetahování - a pravděpodobně byste měli pravdu. Ale v zákulisí se děje totéž.

Někteří lidé navrhli použít desetinné místo k uložení objednávky, takže můžete použít „2,5“ k vložení záznamu mezi záznamy v pořadí 2 a 3. A zatímco to trochu pomůže, je to pravděpodobně ještě poselejší, protože můžete skončit divná desetinná místa (kde zastavíte? 2,75? 2,875? 2,8125?)

Existuje lepší způsob uložení objednávky v tabulce?

30
Tom Marthenal

Pokud chci přesunout záznam 0 na začátek, musím změnit pořadí každého záznamu

Ne, existuje jednodušší způsob.

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

Pokud chci vložit nový záznam uprostřed, musím po každém záznamu změnit pořadí každého záznamu

To platí, pokud nepoužíváte datový typ, který podporuje hodnoty „mezi“. Float a numerické typy umožňují aktualizovat hodnotu, řekněme, 2.5. Ale varchar (n) funguje také. (Přemýšlejte „a“, „b“, „c“; pak si promyslete „ba“, „bb“, „bc“.)

Pokud chci odstranit záznam, musím po každém záznamu změnit pořadí všech záznamů

Ne, existuje jednodušší způsob. Stačí smazat řádek. Zbývající řádky se budou stále třídit správně.

Je snadné si představit situace jako:

Dva záznamy mají stejné pořadí

Tomu může zabránit jedinečné omezení.

Mezi záznamy jsou mezery v pořadí

Mezery nemají žádný vliv na to, jak dbms třídí hodnoty ve sloupci.

Někteří lidé navrhli použít desetinné místo k uložení objednávky, takže můžete použít „2,5“ k vložení záznamu mezi záznamy v pořadí 2 a 3. A zatímco to trochu pomůže, je to pravděpodobně ještě poselejší, protože můžete skončit divná desetinná místa (kde zastavíte? 2,75? 2,875? 2,8125?)

Nezastavíte se, dokud nebudete mít. Dbms má no problém třídění hodnot, které mají 2, 7 nebo 15 míst za desetinnou čárkou.

Myslím, že vaším skutečným problémem je, že chcete viz hodnoty v seřazeném pořadí jako celá čísla. Můžeš to udělat.

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

Je to velmi jednoduché. Musíte mít strukturu „kardinální díry“:

Musíte mít 2 sloupce:

  1. pk = 32bit integer
  2. order = 64bit bigint (notdouble)

Vložit/aktualizovat

  1. Při vkládání prvního nového záznamu nastavte order = round(max_bigint / 2).
  2. Při vkládání na začátek tabulky nastavte order = round("order of first record" / 2)
  3. Při vkládání na konec tabulky nastavte order = round("max_bigint - order of last record" / 2) 4) Při vkládání uprostřed nastavte order = round("order of record before - order of record after" / 2)

Tato metoda má velmi velkou mohutnost. Pokud máte chybu omezení nebo pokud si myslíte, že máte malou mohutnost, můžete znovu vytvořit sloupec objednávky (normalizovat).

V maximální situaci s normalizací (s touto strukturou) můžete mít "kardinální díru" v 32 bitech.

Nezapomeňte nepoužívat typy s pohyblivou řádovou čárkou - objednávka musí být přesná hodnota!

8
user2382679

Obecně se objednávka provádí podle některých informací v záznamech, názvu, ID nebo podle toho, co je pro danou situaci vhodné.

Pokud potřebujete speciální řazení, použití celého sloupce není tak špatné, jak by se mohlo zdát. Chcete-li například vytvořit prostor pro záznam na 5. místo, můžete udělat něco jako:

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

Doufejme, že můžete prohlásit sloupec za unique a možná mít postup, jak změnit uspořádání na atomovou. Podrobnosti závisí na systému, ale to je obecná myšlenka.

4
igelkott

... je to pravděpodobně ještě poselejší, protože můžete skončit s divnými desetinnými místy (kde zastavíte? 2,75? 2,875? 2,8125?)

Koho to zajímá? Tato čísla jsou pouze pro počítač, se kterým se musí vypořádat, takže nezáleží na tom, kolik zlomkových číslic mají nebo jak ošklivé se nám jeví.

Použití desetinných hodnot znamená, že pro přesun položky F mezi položkami J a K stačí pouze vybrat hodnoty objednávky pro J a K, pak je průměrovat a poté aktualizovat F. Dva příkazy SELECT a jeden příkaz UPDATE (pravděpodobně se provádí pomocí serializovatelné izolace, aby se zabránilo zablokování).

Pokud chcete ve výstupu vidět celá čísla než zlomky, pak buď vypočítejte celá čísla v klientské aplikaci, nebo použijte funkce ROW_NUMBER () nebo RANK () (pokud je RDBMS zahrnuje).

4

Ve svém vlastním projektu plánuji vyzkoušet řešení podobné řešení s desetinným číslem, ale místo toho použiji bajtová pole:

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']

Myšlenka je taková, že vám nikdy nedojde možné mezilehlé hodnoty, protože a pokud potřebujete více hodnot, jednoduše připojíte k zúčastněným záznamům b"\x00". (int je neomezeno v Python 3, jinak byste si museli vybrat část bajtů na konci k porovnání, za předpokladu, že mezi dvěma sousedními hodnotami, rozdíly by se sbíhaly ke konci.)

Řekněme například, že máte dva záznamy, b"\x00" A b"\x01", A chcete, aby mezi nimi byl záznam. Mezi 0x00 A 0x01 Nejsou žádné dostupné hodnoty, takže k oběma připojíte b"\x00" A nyní mezi nimi máte spoustu hodnot, které můžete použít k vložení nového hodnoty.

>>> 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'\[email protected]', b'\x00\x80', b'\x00\xc0', b'\x01', b'\x02']

Databáze ji může snadno třídit, protože vše končí v lexikografickém pořadí. Pokud záznam odstraníte, je stále v pořádku. V mém projektu jsem však vytvořil b"\x00" A b"\xff" Jako FIRST a LAST záznamy, abych je mohl použít jako virtuální "od" a Hodnoty „do“ pro připojení nebo připojení nových záznamů:

>>> 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']
1
tjb1982

Našel jsem tato odpověď mnohem lepší. Úplně citovat:

Databáze jsou optimalizovány pro určité věci. Rychlá aktualizace řady řádků je jedním z nich. To se stává zvláště pravdou, když necháte databázi fungovat.

Zvážit:

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

A chcete se přesunout Beat It do konce byste měli dva dotazy:

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

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

A to je vše. To se velmi dobře zvětšuje s velmi velkým počtem. Zkuste vložit několik tisíc skladeb do hypotetického seznamu skladeb v databázi a zjistit, jak dlouho trvá přesunutí skladby z jednoho místa na druhé. Protože mají velmi standardizované formy:

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

update table
  set order = ?
  where song = ?

Máte dvě připravená prohlášení, která můžete velmi efektivně znovu použít.

To poskytuje některé významné výhody - pořadí tabulky je něco, o čem můžete důvodovat. Třetí píseň má vždy order 3. Jediným způsobem, jak to zaručit, je použití po sobě jdoucích celých čísel jako pořadí. Použití pseudově propojených seznamů nebo desetinných čísel nebo celých čísel s mezerami vám nedovolí zaručit tuto vlastnost; v těchto případech je jediným způsobem, jak získat n-tou skladbu, uspořádat celou tabulku a získat n-tou desku.

A opravdu, je to mnohem jednodušší, než si myslíte. Je snadné zjistit, co chcete dělat, vygenerovat dva aktualizační příkazy a pro ostatní lidi se podívat na tyto dva aktualizační příkazy a uvědomit si, co se děje.

1
vedant