Redis 데이터 구조의 점프 테이블에 대한 자세한 설명-Redis-php.cn

Redis Tutorial 칼럼에서는 Redis 데이터 구조의 점프 테이블에 대해 자세히 설명하겠습니다. 도움이 필요한 친구들에게 도움이 되길 바랍니다!

Redis 데이터 구조의 점프 테이블에 대한 자세한 설명

머리말

: 점프 목록 순서가 지정된 데이터 구조이며 노드에 빠르게 액세스하기 위해 각 노드의 다른 노드에 대한 여러 포인터를 유지합니다. 이런 식으로 우리가 이해하기 어려울 수 있지만 먼저 연결 목록을 기억할 수 있습니다.

1. 점프 테이블 리뷰

1.1 점프 테이블이란

단일 연결 리스트의 경우, 연결 리스트에 저장된 데이터를 순서대로 나열하더라도 그 안의 특정 데이터를 찾으려면 처음부터 시작 연결리스트의 테일 순회. 이렇게 하면 검색 효율성이 매우 낮고 시간 복잡도가 매우 높아 O(n)이 됩니다.

Redis 데이터 구조의 점프 테이블에 대한 자세한 설명

검색 효율성을 높이고 싶다면 연결 목록에 인덱스를 구축하는 것을 고려해 볼 수 있습니다. 두 개의 노드마다 한 개의 노드를 이전 레벨로 추출하고, 추출된 레벨을 인덱스라고 부릅니다. Redis 데이터 구조의 점프 테이블에 대한 자세한 설명

이때 노드 8을 찾고 싶다고 가정합니다. 먼저 인덱스 레이어에서 순회할 수 있습니다. 인덱스 레이어에서 값이 7인 노드로 순회하면 다음 노드는 9라는 것을 알 수 있습니다. 따라서 우리가 찾고자 하는 노드 8은 이 두 노드 사이에 있어야 합니다. 우리는 연결리스트 수준으로 내려가 노드 8을 찾기 위해 계속 탐색했습니다. 원래는 단일 연결 리스트에서 노드 8을 찾기 위해 8개의 노드를 순회해야 했지만 이제 1단계 인덱스를 사용하면 5개의 노드만 순회하면 됩니다.

이 예를 보면, 인덱스 레벨을 추가한 후 노드를 검색해야 하는 노드 수가 줄어들고, 이는 인덱스 레벨도 마찬가지로 검색 효율성이 향상된다는 것을 알 수 있습니다. 추가됩니다.

Redis 데이터 구조의 점프 테이블에 대한 자세한 설명

사진을 보면 검색 효율성이 다시 향상되었음을 알 수 있습니다. 이 예에서는 데이터가 매우 적습니다. 데이터 양이 많을 경우 다단계 인덱스를 추가하면 검색 효율성이 크게 향상될 수 있습니다.

Redis 데이터 구조의 점프 테이블에 대한 자세한 설명

이 연결리스트와 다단계 인덱스를 더한 구조가 점프리스트입니다!

2. Redis 점프 테이블

Redis는 정렬된 세트 키의 기본 구현 중 하나로 점프 테이블을 사용합니다. 긴 문자열을 비교할 때 Redis는 순서가 지정된 세트 키의 기본 구현으로 점프 테이블을 사용합니다. 여기서 우리는 질문에 대해 생각해 볼 필요가 있습니다. 요소 수가 많거나 멤버가 상대적으로 긴 문자열일 때 Redis가 점프 테이블을 사용하여 구현하는 이유는 무엇입니까? 위에서 살펴본 바와 같이 점프 리스트는 검색 효율성을 높이기 위해 연결 리스트를 기반으로 다단계 인덱스를 추가한다는 것을 알 수 있지만 이는 시공간적 해결책이므로 필연적으로 문제가 발생합니다 - 인덱스는 메모리를 차지합니다. 원래 연결 리스트는 매우 큰 객체를 저장할 수 있지만 인덱스 노드는 키 값과 몇 개의 포인터만 저장하면 되며 객체를 저장할 필요가 없습니다. 따라서 노드 자체가 상대적으로 크거나 요소 수가 많은 경우. 상대적으로 크기 때문에 장점은 필연적으로 확대되고 단점은 무시될 수 있습니다.

2.1 Redis에서 스킵 테이블 구현

Redis의 스킵 테이블은 Redis 데이터 구조의 점프 테이블에 대한 자세한 설명와 Skiplist의 두 가지 구조로 정의됩니다. Redis 데이터 구조의 점프 테이블에 대한 자세한 설명 구조는 스킵 테이블 노드를 나타내는 데 사용되고 zskiplist 구조는 스킵 테이블 관련 정보를 저장하는 데 사용됩니다. 노드(예: 노드) 번호, 헤드 노드 및 테일 노드에 대한 포인터 등

위 그림은 건너뛰기 목록의 예를 보여 주며, 가장 왼쪽의 것은 다음 속성을 포함하는 건너뛰기 목록 구조입니다.

RedisRedis 데이터 구조의 점프 테이블에 대한 자세한 설명

header: 점프 테이블의 헤드 노드를 가리킵니다. 이 포인터 프로그램을 통해 헤드 노드를 찾는 시간 복잡도는 O(1)

tail: 점프 테이블의 테일 노드를 가리킵니다. 이 포인터 프로그램은 테이블 끝에서 노드를 찾는 시간 복잡도가 O(1)
레벨입니다. 현재 점프 테이블에서 레이어 수가 가장 많은 노드의 레이어 수를 기록합니다. 헤드 노드의 레이어는 포함되지 않음), 이를 통해 O(1) 시간 복잡도에서 레이어 높이가 가장 좋은 노드의 레이어 번호를 얻을 수 있다.
length: 점프 테이블의 길이, 즉 현재 점프 테이블에 포함된 노드 수를 기록합니다(헤더 노드는 계산되지 않음). 이 속성을 통해 프로그램은 시간 복잡도 내에서 점프를 반환할 수 있습니다. O(1) 테이블의 길이입니다.

구조의 오른쪽에는 다음 속성을 포함하는 4개의 Redis 데이터 구조의 점프 테이블에 대한 자세한 설명 구조가 있습니다.
레벨(레벨):

노드는 노드의 각 레이어를 표시하기 위해 1, 2, L3 및 기타 단어로 표시됩니다. . L1은 첫 번째 레이어를 나타내고 L은 두 번째 레벨을 나타냅니다.

각 레이어에는 정방향 포인터와 범위라는 두 가지 속성이 있습니다. 정방향 포인터는 테이블 끝에 있는 다른 노드에 접근하는 데 사용되며, 범위는 정방향 포인터가 가리키는 노드와 현재 노드 사이의 거리를 기록합니다(범위가 클수록 거리가 멀어집니다). 위 그림에서 연결선에 숫자가 있는 화살표는 정방향 포인터를 나타내며, 그 숫자가 스팬(span)입니다. 프로그램이 테이블의 처음부터 테이블의 끝까지 이동할 때 레이어의 앞쪽 포인터를 따라 접근이 진행됩니다.

새로운 점프 테이블 노드가 생성될 때마다 프로그램은 거듭제곱 법칙에 따라 레벨 배열의 크기로 1에서 32 사이의 값을 무작위로 생성합니다(숫자가 클수록 발생 확률은 작아집니다). 레이어의 "높이"입니다.
뒤로 포인터:

노드에서 BW로 표시된 노드의 뒤로 포인터로, 현재 노드에 위치한 이전 노드를 가리킵니다. 백 포인터는 프로그램이 테이블의 끝에서 시작으로 이동할 때 사용됩니다. 정방향 포인터와의 차이점은 각 노드에는 역방향 포인터가 하나만 있으므로 한 번에 한 노드만 뒤로 이동할 수 있다는 것입니다.
점수:

각 노드의 1.0, 2.0, 3.0은 노드가 저장한 점수입니다. 점프 테이블에서는 저장된 점수에 따라 노드가 작은 것부터 큰 것 순으로 배열됩니다.
멤버 객체(oj):

각 노드의 o1, o2, o3은 해당 노드가 저장한 멤버 객체입니다. 동일한 점프 테이블에서 각 노드가 저장한 구성원 개체는 고유해야 하지만 여러 노드가 저장한 점수는 동일할 수 있습니다. 동일한 점수를 가진 노드는 구성원 개체의 크기에 따라 사전순으로 정렬됩니다. 더 작은 멤버 개체를 가진 노드는 앞쪽(테이블의 머리 부분에 가까운 방향)에 배열되고, 더 큰 멤버 개체를 가진 노드는 뒤쪽(테이블의 끝에 가까운 방향)에 배열됩니다.

Redis 데이터 구조의 점프 테이블에 대한 자세한 설명

2.2 Redis 점프 테이블의 일반적인 작업의 시간 복잡도

작업	시간 복잡도
점프 테이블 만들기	O(1)
출시 결정 점프 목록과 그 안에 포함된 노드	O(N)
주어진 멤버와 점수로 새 노드를 추가하세요	평균 O(logN), 최악의 경우 O(logN) (N은 점프의 길이입니다) list)
해당 멤버와 스킵 리스트의 점수가 포함된 노드를 삭제합니다.	Average O(logN), 최악의 경우 O(logN) (N은 스킵 리스트의 길이)
해당 멤버를 반환합니다. 그리고 점수 테이블에 있는 값을 가진 노드의 순위	평균 O(logN), 최악의 경우 O(logN) (N은 점프 테이블의 길이)
주어진 순위에 있는 노드를 반환	평균 O(logN), 최악의 경우 O(logN) (N은 점프 목록의 길이)
점수 범위가 주어지면 이 범위와 일치하는 점프 목록의 첫 번째 노드를 반환합니다	O(1)
given 점수 범위를 설정하고 이 범위와 일치하는 점프 목록의 마지막 노드를 반환합니다	평균은 O(logN), 최악은 O(logN)입니다(N은 점프 목록의 길이)
점수 범위가 주어지면 점프 목록에서 이 범위 내의 모든 노드를 제외하고 평균 O(logN), 최악의 경우 O(logN)(N은 점프 목록의 길이) 주어진 순위 범위에서 모두 제거됩니다. 점프 목록의 노드 이 범위	O(N) 내의 모든 노드, N은 나눌 노드 수
0~15, 20~28 등과 같은 점수 범위가 주어진 경우 점프 테이블에 있는 하나 이상의 노드의 점수가 이 범위 내에 있으면 1이 반환되고, 그렇지 않으면 0이 반환됩니다	O(N), N은 제거할 노드 수
이 글의 핵심 점프 목록은 단일 연결 목록과 인덱싱을 기반으로 구현됩니다. 점프 테이블은 공간과 시간을 교환하여 검색 속도를 향상시킵니다. Redis Ordered Set은 노드가 실행될 때 점프 테이블을 사용하여 구현됩니다. 요소가 크거나 요소 수가 많습니다 Redis의 스킵 테이블 구현은 zskiplist와 zskiplistnode의 두 가지 구조로 구성됩니다. 그 중 zskiplist는 스킵 테이블 정보(예: 테이블 헤더 노드, 테이블 테일 노드, 길이)를 저장하는 데 사용됩니다. ), zskiplistnode는 스킵 테이블 노드를 나타내는 데 사용됩니다. Redis 각 점프 테이블 노드의 레이어 높이는 1에서 32 사이의 임의의 숫자입니다. 동일한 점프 목록에서 여러 노드가 동일한 점수를 포함할 수 있지만 멤버는 각 노드의 객체는 점프 목록에서 고유해야 합니다. 노드는 점수에 따라 정렬되며, 점수가 동일할 경우 구성원 객체의 크기에 따라 노드가 정렬됩니다. 요약 점프 테이블은 우리에게 다소 생소한 데이터 구조일 수 있습니다. 본 글에서는 스킵 테이블의 데이터 구조를 간략히 소개하고 Redis에서 스킵 테이블의 활용을 분석한다. 다음 기사에서는 Redis에서 사용되는 데이터 구조 정수 컬렉션을 계속해서 공유할 것입니다. 계속 지켜봐주세요!