RDBMS에서 정렬 된 목록에 가장 적합한 데이터 구조는 무엇입니까?

Question

나는 수백만 항목의 주문 목록을 MySQL 데이터베이스에 저장하고 있습니다. 합리적으로 자주 항목을 목록에 추가하거나 목록에서 제거해야합니다. 마찬가지로 항목 목록 내의 위치를 ​​결정해야합니다. 나는 읽기/쓰기 비율이 약 50:50이라고 말하고 싶다.

링크드 목록 모델로 시작하여 [1]과 거기에서 논의 된 다양한 모델을 읽었습니다. 엄격한 연결 목록의 경우 인접 목록 모델은 정상적으로 작동하지만 읽기/쓰기 비율이 어느 정도 동일하기 때문에 표준 연속 목록을 사용하여 나누기 및 정복 방식을 사용했습니다.

전체 목록 (대략 ~ 10000)의 '버킷'으로 분류하고, 버킷 크기와 주 목록 내의 상대 위치 인덱스를 유지합니다. 각 항목은 특정 버킷에 할당되고 해당 버킷 내에서의 위치를 ​​추적합니다.

이 방법을 사용하면 항목의 위치는 목록에서 항목의 버킷을 선행하는 버킷의 크기를 합한 다음 자체 버켓 내에 항목의 위치를 ​​추가하여 결정됩니다. 목록에서 항목을 삽입/제거하려면 결과 항목의 '이동'이 항목이 추가되거나 제거되는 버킷에 지역화됩니다. 해당 버킷의 크기도 그에 따라 업데이트해야합니다.

이 접근법 (버킷 크기)에는 일부 비정규 화가 발생하며 트랜잭션이 포함되어 있어도 기본적으로 스레드로부터 안전하지는 않습니다. 제거/삽입 중에 항목 테이블을 쿼리하여 버킷 위치를 결정해야하기 때문입니다. 그 아이템의 버킷에있는 다른 모든 아이템에 대해 '교대'를 수행하도록 업데이트됩니다. 이러한 동작이 원자 적 (저장 프로 시저를 통한 어쩌면?)이 아니라면 일관되게 교착 상태가됩니다.

RDBMS에서 이러한 종류의 데이터를 유지하는 데 더 효과적인 방법이 있습니까? 스레드 안전 문제는 큰 골치 거리를 불러 일으키고 있으며 저장 프로 시저를 사용하도록 강요하는 것보다이 문제를 해결하는 더 좋은 방법이되어야한다고 생각합니다.

많은 감사, 매트.

[1] Database Structure for Tree Data Structure

Answer 1

링크 된 목록 (안 계층)이 필요한 경우, 당신은 내 블로그에이 문서에서 설명하는 방법 사용할 수 있습니다

• Sorting lists

을

,이 간단한 쿼리와 함께 :

SELECT @r AS _parent, 
     @r := (
     SELECT id 
     FROM t_list 
     WHERE parent = _parent 
     ) AS id 
FROM (
     SELECT @r := 0 
     ) vars, 
     t_list 

id 및 parent에 효율적으로 정의 된 UNIQUE 색인이 있는지 확인하십시오.

id에서 검색을 시작하려면 @r := 0을 @r := @id_of_record_to_start_with으로 바꾸십시오. 이 '부모'아니, 사실은 '이전'연결리스트 인 경우

SELECT COUNT(*) 
FROM (
     SELECT @r AS _id, 
       @r := (
       SELECT parent 
       FROM t_list 
       WHERE id = _id 
       ) AS id 
     FROM (
       SELECT @r := @item_id 
       ) vars, 
       t_list 
     ) q