redis 데이터 구조의 intset 인 스 턴 스 상세 설명

redis 데이터 구조의 intset 인 스 턴 스 상세 설명
 redis 에서 intset 는 주로 정수 치 를 저장 하 는 데 사 용 됩 니 다.바 텀 은 배열 로 데 이 터 를 저장 하기 때문에 집합 에 데 이 터 를 추가 할 때 집합 을 확대 하고 이전 하 는 작업 이 필요 합 니 다.따라서 데이터 양 이 많 지 않 을 때 만 redis 는 이 데이터 구 조 를 사용 하여 정수 집합 을 저장 합 니 다.그 구체 적 인 바 텀 데이터 구 조 는 다음 과 같다.

typedef struct intset {
  
  //     
  uint32_t encoding;

  //          
  uint32_t length;

  //        
  int8_t contents[];

} intset;

      정수 집합 은 주로 세 가지 속성 이 있 습 니 다.encoding 은 현재 집합 을 저장 하 는 인 코딩 으로 16 비트,32 비트 와 64 비트 세 가지 가 있 습 니 다.length 는 현재 정수 집합 에 저 장 된 데이터 수량 을 저장 합 니 다.contents 속성 은 구체 적 인 데 이 터 를 저장 하고 모든 데이터 가 차지 하 는 자릿수 는 encoding 속성 으로 지정 합 니 다.
      여기 서 주로 설명 해 야 할 것 은 redis 의 intset 에서 데 이 터 는 어 릴 때 부터 큰 순서 로 저장 되 기 때문에 데이터 에 대한 조 회 는 이분법 으로 조회 할 수 있 고 구체 적 인 검색 코드 는 다음 과 같다.

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
  int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
  int64_t cur = -1;

  /* The value can never be found when the set is empty */
  //    is       
  if (intrev32ifbe(is->length) == 0) {
    if (pos) *pos = 0;
    return 0;
  } else {
    /* Check for the case where we know we cannot find the value,
     * but do know the insert position. */
    //           ，   value             
    //    value          ，
    //       value            
    if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
      if (pos) *pos = intrev32ifbe(is->length);
      return 0;
    //           ，   value             
    //    value          ，
    //                  
    } else if (value < _intsetGet(is,0)) {
      if (pos) *pos = 0;
      return 0;
    }
  }

  //             
  // T = O(log N)
  while(max >= min) {
    mid = (min+max)/2;
    cur = _intsetGet(is,mid);
    if (value > cur) {
      min = mid+1;
    } else if (value < cur) {
      max = mid-1;
    } else {
      break;
    }
  }

  //           value
  if (value == cur) {
    if (pos) *pos = mid;
    return 1;
  } else {
    if (pos) *pos = min;
    return 0;
  }
}

      이 밖 에 정수 집합 에서 구체 적 으로 설명해 야 할 두 가지 조작 은 업그레이드 와 강등 이다.업 그 레이 드 는 낮은 인 코딩 의 정수 집합 에 자릿수 가 높 은 수 치 를 추가 하면 정수 집합 에 있 는 모든 요 소 를 높 은 자릿수 의 인 코딩 형식 으로 확대 하고 새로 추 가 된 요 소 를 지정 한 위치 에 삽입 하 는 것 을 말한다.강등 이란 정수 집합 에서 유일 하 게 높 은 비트 의 요 소 를 삭제 할 때 나머지 요 소 를 낮은 비트 의 인 코딩 형식 으로 바 꾸 는 것 을 말한다.그러나 속 도 를 높이 기 위해 redis 에 서 는 남 은 요 소 를 위해 메모 리 를 재배 치 하고 인 코딩 을 하지 않 는 다.다만 이 높 은 비트 원 소 를 삭제 하고 남 은 요소 에 메모 리 를 재배 치 한 다음 데 이 터 를 이전 할 뿐이다.그림 은 inset 에서 데 이 터 를 저장 하 는 예시 입 니 다.

궁금 한 점 이 있 으 시 면 메 시 지 를 남기 거나 본 사이트 의 커 뮤 니 티 에 가서 토론 을 교류 하 세 요.읽 어 주 셔 서 감사합니다. 도움 이 되 셨 으 면 좋 겠 습 니 다.본 사이트 에 대한 지지 에 감 사 드 립 니 다!