스킵 리스트는 균형을 유지하기 위해 회전 대신 동전 던지기를 사용했다

균형 트리로 구축된 정렬 구조는 각 업데이트 후 재균형을 맞춰야 하며, 이는 회전, 재색칠, 세심한 불변식 유지를 의미한다. 이 모든 것은 틀리기 쉽고 병렬화하기 어렵다.

스킵 리스트는 그 기계 장치를 확률적 규칙으로 대체한다. 각 노드에는 급격히 감소하는 분포에서 추출한 레벨이 부여되므로 대부분은 낮고 소수는 높으며, 검색은 더 낮은 레벨의 긴 구간을 건너뛴 뒤 아래로 내려갈 수 있다.

레벨이 무작위이므로 레벨당 노드 수의 기대값은 기하 분포를 따르며, 검색, 삽입, 삭제 모두 기대값이 O(log n)에 해당한다. 코드는 짧고, 사후에 수행해야 할 부가 관리가 없다.

회전이 아니라 동전 던지기로 균형을 유지한다

무작위 레벨은 재균형 코드 없이 높이 한계를 제공한다.

국소적이고 잠금에 친화적인 연산은 병렬화를 쉽게 만든다.

단순성은 유지하고 틀리기 쉬운 불변식이 적다는 것을 의미한다.

결정론적 재균형이 비용이 많이 들고 오류가 발생하기 쉬운 부분이라면, 그것을 정직한 무작위성으로 대체하라. 국소적이고 단순한 연산은 손으로 유지하는 불변식과 동일한 기대 성능을 제공한다.

스킵 리스트는 라이브러리와 데이터베이스에서 트리에 대한 표준 대안이 되었으며, 가장 유명한 것은 Redis의 정렬 집합으로, 여기서 단순성은 동시성과 예측 가능한 성능을 돕는다.