스킵 리스트

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

연결 리스트의 특성과 한계

• 어떤 위치든 O(1)시간만에 삽입/삭제가 가능.
• O(n)보다 빠르게 검색이 불가능함.  (이분검색 불가능, eg.)
• 중간범위를 점프하기 어려움.

스킵 리스트

정렬된 연결 리스트에 이분검색 이론을 접합시킨 유사 연결 리스트.

추가적인 메모리를 지불하고, 평균 O(log n)에 해당하는 검색속도를 얻을 수 있다.

스킵 리스트의 특성

• 정렬된 상태의 연결 리스트에서만 사용가능
• 탐색범위를 절반씩 줄이기 위해, log(n)개의 레벨을 갖음.
• 각 레벨마다 헤더/센티넬 노드를 갖음.
  
• 각 데이터 노드는 유동적으로 최대 log(n)개의 포인터를 갖음.
• 보다 더 많은 메모리를 소요하지만, 이분검색 이론을 적용시킬 수 있음.  (로그시간)
• 레벨관리를 위해 삽입/삭제마다 추가적인 작업이 필요함.  (선형시간)

이상적인 스킵 리스트

• 전체 레벨수는 O(log n)개 그리고 최대 32개가 적당함.  (효율적인 이분탐색을 위해.)
• n+1번째 레벨의 노드수는, n번째 레벨의 1/2(성능 이상적) 또는 1/4(안정적)을 사용.
• 각 레벨마다 헤더/센티넬 노드를 가지고 있어야 함.
• 각 레벨마다 데이터를 중복시키는 것이 아닌, 포인터를 추가로 갖는식으로 구현한다. 

현실과의 타협 (확률론 이용 - Randomize 스킵 리스트)

매번 삽입/삭제가 될 때 마다, 

각 레벨의 노드수를 이상적으로 유지하기 힘듬.

높은 레벨의 노드가 삭제되면, 전체성능에 큰 영향을 끼치지만.

이상적인 노드 개수를 파악하는 오버헤드가 크므로,

별다른 처리없이 삭제하도록 냅둔다.

반면 새로운 노드가 삽입될 때 마다,

이상적인 노드 개수를 파악하는 오버헤드가 크므로,

확률적으로 해당 노드의 레벨을 결정하도록 한다.

• 레벨 1이 될 확률 :  p^0 * (1-p)
• 레벨 2이 될 확률 :  p^1 * (1-p)
• 레벨 n이 될 확률 :  p^n-1 * (1-p)

p는 보통 0.5를 채용하는데,

p가 0에 가까워질수록 낮은 레벨의 분포가 많아진다.

확률론에 기반했므로,  운이 나쁘다면 (모든 노드의 레벨이 동일한 경우 eg.) 

모든 면에서 연결 리스트보다 불리하다.

다만 이렇게까지 운나쁠 확률은 굉장히 적다.

길이 100 짜리 리스트가 이렇게 될 확률은,

동전을 100개 던져 전부 앞면이 나올 확률과 비슷하다.

랜덤 스킵 리스트 : 삽입

• 데이터가 삽입될 위치 검색

• 데이터 삽입  (단, 노드의 레벨은 확률로 결정.)

랜덤 스킵 리스트 : 삭제

• 제거될 데이터의 위치 검색

• 데이터 제거 (각 레벨의 밸런싱을 무시하는것에 유의.)

랜더마이즈 스킵 리스트의 특성

• 확률적인 노드레벨 분포.
• 이분검색을 사용할 수 있는 자료구조 중,  삽입/삭제 오버헤드가 적음.
• 따라서 병렬 프로그래밍에서 삽입/삭제에 필요한 락의 길이가 짧음.
• 포인터, 노드별로 로컬하게 락을 걸 수 있어서 충돌확률도 더 적음.

인덱스 스킵 리스트

스킵 리스트 계열에서 인덱스를 사용할 수 있도록 개선된 버전.

역시 병렬 프로그래밍에서 우월하기 때문에, 

실제로 키-값 데이터베이스인 Redis에서 사용된다. 

다만 인덱스 관리비용이 소요됨.

고려사항

스킵 리스트가 유용한 경우

• 멀티 쓰레드에서 빈번하게 삽입/삭제가 발생할 때 좋음.
• 순차적으로 탐색할 필요가 많은 경우 좋음. (타임라인 eg.)

스킵 리스트가 유용하지 않은 경우

• 정렬할 필요가 없을 땐, 해쉬 테이블을 사용하는 것이 좋음.
• cache miss/fragmentation 등으로 인해 B-Tree보다 느리게 동작하는 경우가 있음.

참고문헌

• 슬라이드 쉐어 - 김정욱 - 
• 메릴랜드 대학 자료구조론 강의  -스킵 리스트-