Skip List를 어디에 쓸 수 있을까

Skip List

일반 Linked List는 정렬이 되어있더라도 그 이점을 살리지 못하고, 원하는 노드를 찾기 위해 헤드부터 끝까지 쭉 돌아야 한다. == O(n).

Skip List는 일반 Linked List에 level의 개념을 추가해서 마치 binary search tree처럼 탐색 속도를 줄이는 자료구조라고 할 수 있다

우선 생긴 것은 아래와 같다.

출처: https://en.wikipedia.org/wiki/Skip_list#/media/File:Skip_list.svg

각 노드마다 위쪽으로 길게 포인터가 붙어있는데, 이것을 레벨이라고 한다. (위에서부터 0이라 하는지, 밑에서부터 0이라 하는지 등의 구체적인 것은 구현에 따라 달라질 수 있음)

먼저 find를 생각해보자.

위의 Skip List에서 7를 찾고 싶다고 생각하면, 기존의 Linked List에선 7개의 노드를 봐야한다.

(1)  1 보고, 아니네? 다음

(2)  2 보고, 아니네? 다음

(3)  3 보고, 아니네? 다음

…

(7)  6 보고, 아니네? 다음

(8)  7 보고, 맞네? 찾았다!

물론 원하는 게 바로 안 나오면 n개까지 찾다가 없다고 알아낼 수 있다.

7을 7번만에 찾았다는 건 운이 좋은 경우이고,

정렬이 되어있더라도 이 사실은 크게 변하지 않는다(일반적인 Linked List라고 하면).

반면 Skip List에서 8를 찾고 싶다면 1 -> 4 -> 6 -> 7 을 거쳐 찾을 수 있다.

(1)  1 보고, 나보다 작네? 가장 높은 레벨(4)이 가리키는 애를 보자

(2)  Null을 가리키고 있네.. 그러면 다음 낮은 레벨(3)을 보자.

(3)  4를 기리키고 있네? 내가 찾고자하는 8보다 작으니 이동하자

(4)  4에서 같은 레벨의 다음 것을 보니 6을 가리키고 있네? 8보다 작으니 이동하자

(5)  6에서 같은 레벨의 다음 것을 보니 Null을 가리키고 있네? 레벨을 하나 낮추자(2).

(6)  7을 가리키고 있네? 찾았다!

위의 Skip List로 예를 들어서 단계의 수만 보면 별로 차이가 없다고 느낄 수 있다.

하지만 Skip List는 무려 정렬을 이용할 수 있다.

마치 Binary Search Tree 처럼 정렬을 이용해서 Linked List임에도 불구하고 빠르게 서치할 수 있는 것이다.

그러면 구현은 어떻게 하지?

각 노드마다의 레벨이 있는데, 이 레벨을 정하는 게 문제다.

이 레벨은 동전을 던져서 정하면 된다.

그냥 랜덤하게 정하는 것이다.

노드의 레벨을 정할 때마다 랜덤하게 만들면 전체적으로 보았을 때 레벨이 골고루 분포되고 우리가 원하는, 마치 Binary Search Tree를 쭉 늘어놓은 듯한, Skip List가 나온다고 한다.

이 Skip List의 내용은 수업 중에도 깊게 다루기 보단 개념을 소개하는 느낌으로 가서 보다 자세한 내용은 더 공부가 필요하다.

Skip List는 어디에 쓰지?

사실 수업 때 Skip List를 보면서 처음 든 생각은 ‘어디에 쓸까’였다.

레벨을 랜덤하게 설정했는데 아무튼 바이너리 서치 트리처럼 빠르게 찾을 수 있다는 것도 잘 이해가 안됐고

그럼 그냥 만들기도 쉬운 바이너리 서치 트리 만들면 되는 거 아닌가? 라는 생각도 들었다.

우매한 한명의 비전공생의 생각에 불과했다.

교수님은 Randomized된 자료구조의 장점을 이야기하며 Skip List의 사용처 느낌을 잡아주셨다(교수님도 사용처를 정확히 모르셔서 이후 보충자료를 보내주셨다).

Randomized된 자료구조는 공격에 강하다는 것이다.

예를 들어 어떤 서비스에서 바이너리 서치 트리를 사용한다고 생각해보자.

자료형에 따라 다르겠지만 극도로 단순하게 생각해서 정수형 자료구조라 했을 때,

우리는 비교적 쉽게 특정 값의 위치를 파악할 수 있다.

예를 들면, 가장 서치가 오래 걸리는 값의 위치.

그러면 그런 값을 반복해서 요청한다면 나름의 공격이 되는 것이다.

이게 개념적으로 맞는지는 모르겠는데 그나마 이해할 수 있는 설명이었다.

예시로만 받아들이자.

아무튼 이것과 다르게 Randomized된 자료구조는 특정 값의 위치를 파악하기 힘들어

공격에 내성이 있다는 것이다.

이 정도가 교수님의 설명이었고 추가적으로 주변 현업 개발자분들께 실제 사용을 물어보고 알려주신다 하셨다(^^b)

Skip List가 BST에 비해 좋은 점?

추가적으로 교수님이 읽을 거리를 주셨는데, 여기서 결정적인 Skip List의 사용을 알 수 있었다.

https://stackoverflow.com/questions/256511/skip-list-vs-binary-search-tree

Skil List와 BTS를 비교한 글인데, 요약하자면

Skip List는 concurrent access / modification 에 적합하다는 내용이다.

concurrent는 주로 병행으로 번역하는데, 우리가 알고 있는 parallel(병렬)과는 다른 뜻이다.

Throughput과 관련이 있다고 생각하면 된다.

같은 일을 나눠서 하면 parallel이고, 같은 일을 동시에 여러 개가 수행하도록 하면 concurrent이다.(더 자세한 건 여기서 다룰 수 없음)

아무튼 Skip List가 concurrent에 적합한 이유는, 일종의 lock-free 자료구조에 가깝기 때문이다.

BTS(red black tree 기준)은 수정되면 rebalance를 해주면서 트리의 모든 부분이 영향을 받을 수 있기 때문에 많은 트리 노드에 대한 mutex lock이 필요하다.

Skip List는 삽입시 훨씬 더 좁은 범위와 관련이 있다(far more localized),.

영향을 받는 노드에 직접적으로 연결되어 있는 노드들만 lock되면 되기 때문이다.

Linked List에 삽입 시 삽입할 위치와 한쪽 노드(더블 링크드면 양쪽)만 건드리면 된다는 걸 알 것이다.

Skip List도 비슷한 원리로 삽입할 곳의 주변 노드들에만 lock을 걸고 수정하면 된다.

(레벨별 포인터 값을 다 수정해주어야 해서 Linked List보단 신경쓸 게 많긴 함)

같은 일을 하는데 lock을 더 적게 걸 수 있다면 당연히 이득을 볼 수 있다.

데이터 삽입 할 때 다른 곳의 데이터를 접근하려면 기다리지 않아도 되고

lock으로 다뤄야할 정보 역시 적어지니 개발이 더 쉬워질 것이다.