관계형 데이터베이스의 순서 표현
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
데이터베이스에 개체 컬렉션이 있습니다.사진 갤러리의 이미지, 카탈로그의 제품, 책의 장 등각 개체는 행으로 표시됩니다.나는 이러한 이미지의 순서를 임의로 지정하고 해당 순서를 데이터베이스에 저장하여 개체를 표시할 때 올바른 순서로 표시되기를 원합니다.
예를 들어, 내가 책을 쓰고 있는데 각 장이 객체라고 가정해 보겠습니다.나는 책을 쓰고 장을 다음 순서로 배치합니다.
소개, 접근성, 형식 vs.기능, 오류, 일관성, 결론, 색인
편집기로 이동한 후 다음 제안 순서와 함께 돌아옵니다.
서론, 형태, 기능, 접근성, 일관성, 오류, 결론, 색인
이 순서를 강력하고 효율적인 방식으로 데이터베이스에 어떻게 저장할 수 있습니까?
나는 다음과 같은 아이디어를 갖고 있지만 그 어느 것도 마음에 들지 않습니다.
정렬.각 행에는 주문 ID가 있으며, 주문이 변경되면(제거 후 삽입을 통해) 주문 ID가 업데이트됩니다.이렇게 하면 검색이 쉬워집니다.
ORDER BY, 하지만 깨지기 쉬운 것 같습니다.// 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연결된 목록.각 행에는 순서대로 다음 행의 ID에 대한 열이 있습니다.순회는 여기에서 비용이 많이 드는 것처럼 보이지만 어떤 방법으로든 사용할 수 있습니다.
ORDER BY내가 생각하지 않는 것.간격 배열.orderingID(#1에서 사용됨)를 크게 설정하여 첫 번째 개체는 100, 두 번째 개체는 200 등이 되도록 합니다.그런 다음 삽입이 발생하면 그냥 위치에 배치하면 됩니다.
(objectBefore + objectAfter)/2.물론, 때때로 균형을 재조정해야 하므로 항목이 너무 가깝지 않도록 해야 합니다(플로트를 사용하더라도 결국 반올림 오류가 발생하게 됩니다).
이 중 어느 것도 나에게는 특별히 우아해 보이지 않습니다.더 좋은 방법이 있는 사람이 있나요?
해결책 9
나는 주로 Django에서 이 문제를 접했기 때문에 다음을 발견했습니다. 이 솔루션 가장 실행 가능합니다.관계형 데이터베이스에서는 이를 수행하는 "올바른 방법"이 없는 것 같습니다.
다른 팁
다른 대안은 (RDBMS가 지원하는 경우) 배열 유형의 열을 사용하는 것입니다.이는 정규화 규칙을 위반하지만 이와 같은 상황에서는 유용할 수 있습니다.내가 아는 배열이 있는 데이터베이스 중 하나는 PostgreSQL입니다.
Rails의 act_as_list 믹스인은 기본적으로 #1에서 설명한 방식으로 이를 처리합니다.position이라는 INTEGER 열(물론 이름으로 재정의할 수 있음)을 찾고 이를 사용하여 ORDER BY를 수행합니다.물건을 다시 주문하려면 위치를 업데이트하세요.내가 그것을 사용할 때마다 그것은 나에게 잘 봉사했습니다.
참고로, 희소 번호 매기기를 사용하면 INSERTS/DELETES에서 항상 위치를 다시 지정할 필요가 없습니다. 예전의 기본과 비슷합니다.위치에 10, 20, 30 등의 번호를 지정할 수 있습니다.10에서 20 사이에 무언가를 삽입해야 하는 경우 위치를 15로 삽입하면 됩니다.마찬가지로 삭제할 때 행을 삭제하고 공백을 남겨둘 수 있습니다.실제로 순서를 변경하거나 삽입하려고 하는데 삽입할 적절한 간격이 없는 경우에만 번호를 다시 매겨야 합니다.
물론 특정 상황에 따라(예:다른 행이 이미 메모리에 로드되어 있는지 여부에 관계없이 간격 접근 방식을 사용하는 것이 합리적일 수도 있고 그렇지 않을 수도 있습니다.
그냥 생각해보면 옵션 #1 대 #3:간격 배열 옵션(#3)은 일반 배열(#1)의 문제만 지연시키지 않나요?어떤 알고리즘을 선택하든, 깨져서 나중에 #3에서 문제가 발생하거나, 작동하고 나서 #1도 마찬가지로 작동해야 합니다.
개체의 키가 다른 테이블에 의해 크게 지정되지 않고 목록이 짧은 경우 도메인의 모든 항목을 삭제하고 올바른 목록을 다시 삽입하는 것이 가장 쉽습니다.그러나 목록이 크고 삭제 속도를 늦추는 데 많은 제약이 있는 경우 이는 실용적이지 않습니다.첫 번째 방법이 실제로 가장 깨끗하다고 생각합니다.트랜잭션에서 실행하면 주문을 망치기 위해 업데이트하는 동안 이상한 일이 발생하지 않는다는 것을 확신할 수 있습니다.
지난 프로젝트에서 이 작업을 수행했지만 가끔 특별히 주문해야 하고 자주 액세스되지 않는 테이블에 대한 작업이었습니다.나는 간격 배열이 가장 좋은 옵션이라고 생각합니다. 왜냐하면 하나의 값을 변경하고 두 값에 대한 쿼리를 포함하는 일반적인 경우 재정렬이 가장 저렴하기 때문입니다.
또한 ORDER BY는 데이터베이스 공급업체에 의해 상당히 최적화될 것이라고 생각하므로 해당 기능을 활용하는 것이 연결 목록 구현과 달리 성능 측면에서 유리할 것입니다.
부동 소수점 숫자를 사용하여 각 항목의 위치를 나타냅니다.
항목 1 -> 0.0
항목 2 -> 1.0
항목 3 -> 2.0
항목 4 -> 3.0
간단한 이등분을 통해 다른 두 항목 사이에 항목을 배치할 수 있습니다.
항목 1 -> 0.0
항목 4 -> 0.5
항목 2 -> 1.0
항목 3 -> 2.0
(항목 4를 항목 1과 2 사이로 이동했습니다.)
컴퓨터 시스템에서 부동 소수점 숫자가 인코딩되는 방식으로 인해 이분법 프로세스는 거의 무한정 계속될 수 있습니다.
항목 4 -> 0.5
항목 1 -> 0.75
항목 2 -> 1.0
항목 3 -> 2.0
(항목 1을 항목 4 바로 뒤의 위치로 이동)
이미 존재하는 경우 우선순위를 위한 "공간을 만드는" 테이블의 트리거를 사용하여 연속적인 숫자를 수행합니다.
나에게도 이런 문제가 있었다.저는 시간적 압박이 심해서(우리 모두는 아니죠) 옵션 #1을 선택했고 변경된 행만 업데이트했습니다.
항목 1을 항목 10으로 바꾸는 경우 두 번만 업데이트하여 항목 1과 항목 10의 주문 번호를 업데이트하세요.나는 그것이 알고리즘적으로 간단하고 O(n) 최악의 경우라는 것을 알고 있지만 최악의 경우는 목록의 전체 순열이 있을 때입니다.그런 일이 얼마나 자주 일어날까요?그건 당신이 대답하는 몫이다.
나도 같은 문제를 겪었고 아마도 적절한 데이터 모델링에 대해 적어도 일주일 동안 고민했지만 마침내 그 문제를 해결했다고 생각합니다.PostgreSQL에서 배열 데이터 유형을 사용하면 주문한 각 항목의 기본 키를 저장하고 주문이 변경될 때 삽입 또는 삭제를 사용하여 그에 따라 해당 배열을 업데이트할 수 있습니다.단일 행을 참조하면 배열 열의 순서에 따라 모든 개체를 매핑할 수 있습니다.
여전히 다소 불안정한 솔루션이지만 옵션 1에서는 변경 사항을 주문할 때 다른 모든 행의 주문 번호를 업데이트해야 하기 때문에 옵션 #1보다 더 잘 작동할 것입니다.
Scheme #1과 Scheme #3은 다음을 제외한 모든 작업에서 동일한 복잡성을 갖습니다. INSERT 쓴다.구성표 #1에는 O(n) 쓰기가 있습니다. INSERT 그리고 구성표 #3에는 O(1) 쓰기가 있습니다. INSERT.
다른 모든 데이터베이스 작업의 복잡성은 동일합니다.
계획 #2는 고려되어서도 안 됩니다. DELETE O(n) 읽기 및 쓰기가 필요합니다.계획 #1과 계획 #3에는 O(1)이 있습니다. DELETE 읽기와 쓰기 모두에 적합합니다.
새로운 방법
요소에 고유한 상위 요소가 있는 경우(예:외래 키 행을 공유하는 경우) 다음을 시도해 볼 수 있습니다.
Django는 데이터베이스에 구애받지 않는 정수 목록 저장 솔루션을 제공합니다. CharField().한 가지 단점은 저장된 문자열의 최대 길이가 다음보다 클 수 없다는 것입니다. max_length, 이는 DB에 따라 다릅니다.
복잡성 측면에서 이는 Scheme #1 O(1) 쓰기를 제공합니다. INSERT, 순서 정보가 상위 요소 행의 단일 필드로 저장되기 때문입니다.
또 다른 단점은 JOIN 이제 순서를 업데이트하려면 상위 행으로 이동해야 합니다.
