Verteenwoordig Bestel in 'n relasionele databasis
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianVra
Ek het 'n versameling van voorwerpe in 'n databasis. Beelde in 'n foto gallery, produkte in 'n katalogus, hoofstukke in 'n boek, ens Elke voorwerp word voorgestel as 'n ry. Ek wil in staat wees om hierdie beelde na willekeur te bestel, stoor dit bestel in die databasis, sodat wanneer ek van die voorwerpe wys, sal hulle in die regte volgorde.
Byvoorbeeld, kom ons sê ek skryf 'n boek, en elke hoofstuk is 'n voorwerp. Ek skryf my boek, en sit die hoofstukke in die volgende volgorde:
Inleiding, toeganklikheid, Form teen Function, foute, konsekwentheid, Gevolgtrekking, indeks
Dit gaan om die redakteur, en kom terug met die volgende voorgestel ten einde:
Inleiding, vorm, funksie, toeganklikheid, konsekwentheid, foute, Gevolgtrekking, indeks
Hoe kan ek slaan hierdie bestel in die databasis in 'n robuuste, doeltreffende manier?
Ek het die volgende idees gehad, maar ek is nie opgewonde oor enige van hulle:
-
skikking. Elke ry het 'n bestel ID, wanneer bestelling verander (via 'n verwydering gevolg deur 'n invoeging), is aan die orde ID's opgedateer. Dit maak herwinning maklik, want dit is net
ORDER BY, maar dit lyk maklik om te breek.// REMOVAL
UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
// INSERTION
UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
UPDATE ... SET orderID=insertionID WHERE ID=addedID -
geskakelde lys. Elke ry het 'n kolom vir die id van die volgende ry in die bestel. Traversal lyk duur hier, al is daar deur een of ander manier om
ORDER BYdat ek nie dink van gebruik. -
Gespasieerde skikking. die tweede stel die orderingID (soos gebruik in # 1) te groot wees, so die eerste voorwerp is 100, 200, ens Dan wanneer 'n inplanting gebeur, jy moet net plaas dit op
(objectBefore + objectAfter)/2. Natuurlik is dit nodig sou wees om af en toe word herbalanseer, so jy hoef nie dinge te naby aan mekaar het (selfs met dryf, jy uiteindelik wil loop in afrondingsfoute).
Nie een van hierdie lyk veral elegant vir my. Is daar iemand het 'n beter manier om dit te doen?
Oplossing 9
Sedert ek meestal het loop in hierdie met Django, het ek gevind hierdie oplossing aan die mees werkbare wees. Dit blyk dat daar geen "regte manier" om dit te doen in 'n relasionele databasis.
Ander wenke
'n ander alternatief sou wees (as jou RDBMS ondersteun dit) om kolomme van tipe skikking gebruik. Terwyl hierdie breek die normalisering reëls, kan dit nuttig in situasies soos hierdie wees. Een databasis wat ek weet wat skikkings is PostgreSQL.
Die acts_as_list mixin in Rails hanteer hierdie basies die manier waarop jy uiteengesit in # 1. Dit lyk vir 'n heelgetal kolom genoem posisie (waarvan jy kan ignoreer om naam natuurlik) en die gebruik van daardie 'n ORDER BY doen. As jy wil hê na re-order dinge wat jy werk die posisies. Dit het my net mooi elke keer as ek dit gebruik gedien.
soort van soos basiese terug in die dag ... jy kan jou posisies 10, 20, 30 nommer -As 'n kant nota, kan jy die behoefte om altyd weer posisionering op insetsels / verwyder deur gebruik te maak van yl nommers verwyder , ens en as jy nodig het om iets in tussen 10 en 20 wat jy net plaas dit met 'n posisie van 15. net so wanneer die verwydering van jy kan net die ry verwyder en laat die gaping te voeg. Jy hoef net te re-nommers doen wanneer jy eintlik die orde te verander of as jy probeer om 'n insetsel doen en daar is geen geskikte gaping te voeg in.
Natuurlik, afhangende van jou spesifieke situasie (bv of jy oor die ander rye reeds in die geheue of gelaai nie) dit mag of nie mag nie sin nie om die gaping benadering gebruik.
Net 'n gedagte oorweeg opsie # 1 vs # 3 : nie die gespasieer verskeidenheid opsie (# 3) net die probleem van die normale reeks uit te stel (# 1)? Wat ook al algoritme wat jy kies, óf dit gebreek, en jy sal in die moeilikheid met # 3 later, of dit werk, en dan # 1 moet net so goed werk.
As die voorwerpe is nie swaar ingesleutel deur ander tafels, en die lyste is kort, die verwydering van alles in die domein en net weer invoeging van die korrekte lys is die maklikste. Maar dit is nie prakties as die lyste is groot en jy het baie van die beperkings te vertraag die delete. Ek dink jou eerste metode is regtig die skoonste. As jy dit uit te voer in 'n transaksie wat jy kan seker wees niks vreemd gebeur terwyl jy in die middel van die update te skroef aan die orde.
Ek het dit in my laaste projek, maar dit was vir 'n tafel wat net af en toe nodig is om spesifiek bestel word, en is nie te dikwels aangevra. Ek dink die afstand verskeidenheid sal die beste opsie wees, want dit herordening sou goedkoopste in die gemiddelde geval wees, net met 'n verandering aan een waarde en 'n soektog op twee).
Ook, sou ek dink ORDER BY sou mooi swaar geoptimaliseer deur databasis verkopers, so gebruik te maak van daardie funksie voordelig vir prestasie sou wees in teenstelling met die geskakelde lys implementering.
Gebruik 'n drywende punt nommer om die posisie van elke item verteenwoordig:
Item 1 -> 0.0
Item 2 -> 1.0
Item 3 -> 2.0
Item 4 -> 3.0
Jy kan enige item te plaas tussen ander twee items deur eenvoudige halveringsmetode:
Item 1 -> 0.0
Item 4 -> 0.5
Item 2 -> 1.0
Item 3 -> 2.0
(Het item 4 tussen items 1 en 2).
Die halveringsmetode proses kan amper onbepaald voortduur as gevolg van die manier drywende punt getalle word geïnkripteer in 'n rekenaarstelsel.
Item 4 -> 0.5
Item 1 -> 0.75
Item 2 -> 1.0
Item 3 -> 2.0
(Skuif item 1 tot die posisie net nadat punt 4)
Ek sal 'n agtereenvolgende aantal doen, met 'n sneller op die tafel dat "maak room" vir 'n prioriteit as dit reeds bestaan.
Ek het hierdie probleem so goed. Ek was onder swaar tyd druk (is ons almal nie) en ek het saam met opsie # 1, en net opgedateer rye wat verander.
As jy item 1 te ruil met item 10, net doen twee updates aan die orde nommers van item 1 en item 10. Ek weet dit is algoritmies eenvoudige werk, en dit is O (n) ergste geval, maar dat die ergste geval is wanneer jy 'n totale permutasie van die lys. Hoe dikwels is dit gaan gebeur? Dit is vir u om te antwoord.
Ek het dieselfde probleem en het waarskynlik spandeer ten minste 'n week myself met betrekking tot die behoorlike data modelle, maar ek dink ek het uiteindelik het dit. Die gebruik van die skikking data type in PostgreSQL, kan jy die primêre sleutel van elke bestel item te stoor en te werk wat verskeidenheid dienooreenkomstig met behulp van invoegings of weglatings wanneer jou bestelling verander. Verwys na 'n enkele ry sal jou toelaat om al jou voorwerpe te karteer gebaseer op die bestel in die skikking kolom.
Dit is nog steeds 'n bietjie woelig van 'n oplossing, maar dit sal waarskynlik werk beter as opsie # 1, sedert opsie 1 vereis opdatering van die order nommer van al die ander rye wanneer bestel veranderinge.
Skema # 1 en Skema # 3 het dieselfde kompleksiteit in elke operasie behalwe INSERT skryf. Skema # 1 het O (n) skryf oor INSERT en skema # 3 het o (1) skryf oor INSERT.
Vir elke ander databasis operasie, die kompleksiteit is dieselfde.
Skema # 2 moet nie eens oorweeg word omdat sy DELETE vereis O (n) lees en skryf. Skema # 1 en skema # 3 het o (1) DELETE vir beide lees en skryf.
New metode
As jou elemente het 'n duidelike ouer element (dit wil sê hulle 'n vreemde sleutel ry deel), dan kan jy probeer die volgende ...
Django bied 'n databasis-agnostikus oplossing vir die stoor van lyste van heelgetalle binne CharField(). Een nadeel is dat die maksimum lengte van die gestoor string nie groter as max_length, wat is DB-afhanklike kan wees.
In terme van kompleksiteit, sal hierdie Skema gee # 1 O (1) skryf vir INSERT, omdat die bestel inligting sal gestoor word as 'n enkele veld in ry die ouer element se.
Nog 'n nadeel is dat 'n JOIN om die ouer ry nou nodig is om bestellings te werk.
