Skip List vs Heap — ZRANK 탐색 해부

대기열의 킬러 연산 "나 몇 번째야?"를 두 자료구조가 어떻게 처리하는지 나란히 본다. · zset.md

1. Skip List — 고속도로 + span 누적 O(log N)

꼭대기에서 시작 → "다음이 목표보다 크면 내려가고, 아니면 전진". 지나온 span을 더하면 순위가 공짜로 나온다.

현재 노드 지나온 경로 목표 도달 span = 바닥층 건너뛴 칸 수
찾을 값(score):
▶ 값을 고르고 "한 단계"를 눌러 탐색을 시작하세요.

Heap (같은 데이터, 배열 스캔)

순위 알려면 선형 탐색0
비교 횟수N
결과 순위—
값으로 노드를 못 찾음 → 전부 세야 함 = O(N)

2. Heap이 같은 질문을 받으면 O(N)

heap엔 "값으로 노드 찾기"가 없다. 배열을 처음부터 훑으며 "목표보다 작은 원소"를 전부 세야 순위가 나온다.

위에서 목표를 정하면 heap이 몇 번 비교하는지 함께 보여줍니다.

3. 한 줄 결론

skip list는 탐색 경로가 곧 순위 계산이라 추가 비용이 0. heap은 최솟값 하나에 최적화하고 나머지를 포기했기에, 중간 순위 조회에선 매번 전부 세야 한다. 대기열은 그 "나머지"를 95% 이상 쓴다.