가까운 연결과 먼 연결
맨 아래 단계는 전체 항목을 순서대로 잇는다. 높은 단계에는 일부 노드만 참여하여 여러 항목을 건너뛰는 경로를 만든다. 모든 노드가 같은 높이를 가져야 하는 것은 아니다. 높은 단계는 탐색의 지름길이고 실제 항목의 정렬 순서는 아래 단계에서도 유지된다.
탐색 경로
높은 단계에서 시작해 목표 키를 넘지 않는 범위까지 앞으로 이동한다. 더 나아가면 목표를 지나칠 때 한 단계 내려가 같은 과정을 반복한다. 예를 들어 4, 11, 19, 28, 36이 있을 때 28을 찾는 경로는 높은 연결의 배치에 따라 달라지지만 키의 대소 비교 원칙은 동일하다.
삽입과 삭제
삽입할 위치를 찾으면서 각 단계에서 앞에 있던 노드를 기록한다. 새 노드의 높이를 정한 뒤 그 노드가 참여할 단계의 연결만 바꾼다. 삭제도 해당 노드를 가리키던 연결을 다음 노드로 이어 준다. 균형 트리의 회전과 다른 방식으로 탐색 경로를 유지한다.
기대값과 보장의 차이
높이를 적절한 확률 분포로 정하면 높은 노드는 드물어지고 탐색 길이의 기대값이 로그 수준이 된다. 특정 배치에서는 연산이 느려질 수 있으므로 기대 시간과 모든 경우의 최악 시간 보장을 구분해야 한다. 같은 키를 같은 순서로 넣더라도 무작위 선택에 따라 내부 연결은 달라질 수 있다.