스킵 리스트 층수·탐색 비용 계산기
원소 수와 승격 확률에서 스킵 리스트의 기대 층수·노드당 포인터·탐색 비용을 계산합니다. p를 낮추면 메모리는 줄지만 탐색이 언제 나빠지는지 표로 확인할 수 있습니다.
노드를 넣을 때 «한 층 더 올릴» 확률입니다. 레디스는 1/4을 씁니다.
기대 층수
9.97층
탐색에 평균 39.9걸음 · 노드당 포인터 1.33개
| 승격 확률 | 층수 | 노드당 포인터 | 탐색 걸음 |
|---|---|---|---|
| 1/2 | 19.9 | 2 | 39.9 |
| 1/e (0.368) | 13.8 | 1.58 | 37.6 |
| 1/4 | 10 | 1.33 | 39.9 |
| 1/8 | 6.6 | 1.14 | 53.2 |
| 1/16 | 5 | 1.07 | 79.7 |
사용 방법
- 1담을 원소 수를 넣습니다.
- 2승격 확률 p를 고릅니다. 노드를 넣을 때 «한 층 더 올릴» 확률입니다.
- 3기대 층수·노드당 포인터·탐색 비용을 확인합니다.
- 4표에서 p를 바꿨을 때 메모리와 탐색이 어떻게 맞바뀌는지 봅니다.
자주 묻는 질문
log_{1/p} n입니다. 승격 확률이 1/2면 log₂ n, 1/4면 log₄ n이라 층이 절반으로 줄어듭니다. 100만 개를 p=1/4로 담으면 10층 남짓이면 됩니다.
메모리가 줄어듭니다. 노드당 평균 포인터가 1/(1−p)이라 p=1/2면 2개, p=1/4면 1.33개입니다. 놀랍게도 탐색 비용은 p=1/2와 p=1/4가 정확히 같아(2/ln2 = 4/ln4), p=1/4는 탐색을 그대로 두고 메모리만 3분의 2로 줄이는 셈입니다.
p = 1/e ≈ 0.368입니다. 기대 탐색 비용 (1/p)·log_{1/p} n에서 n과 무관한 계수 (1/p)/ln(1/p)를 미분하면 그 자리에서 최소가 되고 값은 e ≈ 2.718입니다. 다만 1/2이나 1/4과 차이가 크지 않고 구현이 훨씬 쉬워, 실제로는 동전 던지기(1/2)나 두 비트 보기(1/4)를 씁니다.
회전도 재균형도 없다는 점입니다. 노드를 넣을 때 동전을 던져 층수를 정하는 것이 전부라 구현이 훨씬 짧고, 잠금을 잘게 나누기도 쉽습니다. 레디스의 정렬 집합(zset)이 이 자료구조를 쓰는 이유입니다.
아닙니다. 확률적 보장이라 동전이 계속 뒷면만 나오면 모든 노드가 1층에 머물러 그냥 연결 리스트가 되고 탐색이 O(n)이 됩니다. 그 확률이 아주 작을 뿐이며, AVL이나 레드블랙 트리가 «언제나» O(log n)을 보장하는 것과는 다릅니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 모두 «기대값»입니다. 실제 층수와 탐색 걸음은 동전 던지기 결과에 따라 흔들리며, 여기 나오는 값은 그 평균입니다.
- 탐색 비용 (1/p)·log_{1/p} n은 널리 쓰이는 어림식입니다. 구현에 따라 각 층에서 옆으로 가는 걸음을 세는 방식이 조금씩 달라 실측과 차이가 날 수 있습니다.
- 노드당 포인터 1/(1−p)는 층마다 복사되는 것까지 합친 평균입니다. 실제 메모리에는 값과 부대 자료가 더 붙습니다.
- 실제 구현은 층수에 최댓값을 둡니다. 레디스는 p=0.25에 32층으로, 4³²까지 감당하면서도 운 나쁘게 아주 높은 층이 나와도 메모리가 튀지 않게 막습니다.
- 삭제가 잦으면 층 구조가 처음 만들 때와 달라질 수 있습니다. 스킵 리스트는 삭제 뒤에도 재균형을 하지 않기 때문입니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.