다음과 같은 상황이 있습니다. 수십 개의 스레드가 액세스 할 수있는 균형 이진 검색 트리가 있습니다. 그래서 노드를 삽입하거나 삭제해야 할 때, 동시성 때문에 전체 트리를 잠그고 싶지 않습니다. 시간이 흐르면 다시 균형이 잡히지 않습니다. 트리가 너무 바빠서 사용하지 않을 때 마침내 잠금을 해제하고 균형을 다시 잡을 기회를 얻습니다. 어떻게해야합니까?임의 이진 검색 트리를 다시 조정하는 방법
또는 더 나은 데이터 구조체를 사용할 수 있습니까?
실제로는 Day-Stout-Warren algorithm을 사용하여 균형을 조정할 수 있습니다. 노드 수가 선형이므로 시간이 걸릴 수 있습니다. 또한,이 접근법은 질문을 제기합니다. 즉, 읽는 나무를 재조정하지 않을 때 심하게 불균형하게되고 모든 결과 판독이 O (logN) 대신 O (N)에서 수행되면 어떻게됩니까? ? 사물을 잠그지 않기 위해 몇 시간 동안 성능이 저하되는 것은 괜찮습니까? 성과 우승이 확실합니까?
선형성의 부족을 용인 할 수있는 경우 (즉, 값을 쓰지만 발견되지 않은 직후에 검색 할 때, 결국에는 있지만 100ms-10s가 지나갈 수 있음) 구현할 수 있습니다. 쓰기 "트리 : 모든 쓰기는 하나의 스레드 (재조정)에 의해 수행되고 주기적으로 트리를 복제하여 동시성 제어없이 스레드를 읽을 수있는 읽기 전용 사본으로 복제하면 원자 적으로 게시하면됩니다. 트리가 전체적으로 복사되고 전체적으로 가비지 수집 될 수있는 연속 메모리 청크 위에 구현되는 경우 특히 빠르게 수행 할 수 있습니다.
또 다른 옵션은 동시 대/소문자를 사용하는 것입니다 : 대수 평균 대/소문자 검색/삭제/삽입 시간을 제공하며 더 쉽게 병렬화 할 수 있습니다. 사용하는 경우 표준 잠금 장치가 없습니다 implementation for Java 있습니다. 동시 건너 뛰기 목록 및 균형 검색 트리 here에 대한 자세한 정보를 찾을 수 있습니다. 특히 동시 재조정을 위해 최적화 된 이진 검색 트리 chromatic tree을 찾을 수 있습니다.
나는 나무를 재조정하지 않으면 성능이 좋지 않다. 삽입 후 몇 분 후에 데이터를 찾을 수 없다면 'copy on write'는 내가 생각하지 못한 모든 좋은 해결책입니다. 매 많이 감사드립니다! –
어떻게 이런 상황이 발생 했습니까? 더 나은 데이터 구조는 유스 케이스를 아는 경우에만 결정될 수 있습니다. 트리가 읽혀 지거나 너무 자주 업데이트됩니까? – displayName
노드를 삭제할 때 노드를 삭제 된 것으로 표시하지만 트리에 보관하십시오. 잠금 및 재조정 할 시간이 있으면 이전 트리를 순차적으로 탐색하고 삭제 된 것으로 표시되지 않은 모든 노드에서 새 트리를 작성하십시오. –
@displayName 대부분의 시간대에 트리가 높은 동시성으로 읽히고 있고 동시에 자주 업데이트됩니다. 하지만 몇 시간마다 읽기 동시성이 식어 버리고 잠그는 것이 좋습니다. –