[REDIS] 어떻게 레디 스 키 조회에 대한 O (1) 시간을 주장 하는가?

어떻게 레디 스 키 조회에 대한 O (1) 시간을 주장 하는가?

나는 질문이 있습니다 - 인덱스의 키 값 쌍 조회 -의 카산드라 또는 포스트 그레스에 가정 해 봅시다 - 주위에 일반적으로 O (logn)

출처 : https://github.com/tinkerpop/blueprints/wiki/Graph-Indices.

레디 스 문서에 그 실행 복잡도가 O (1) 상태이다.

출처 : http://redis.io/commands/get http://redis.io/commands/hget

복수의 키 값을 얻는 것은 단지 선형 m이 검색 키의 개수 O (m) http://redis.io/commands/hmget

그게 어떻게 가능해?

해결법

1. ==============================

   1.레디 스는 메모리 저장소이다. 따라서 메모리에 저장하도록 구성되는 데이터 구조 (빠른 랜덤 액세스 가능)를 사용할 수있다.

   레디 스는 메모리 저장소이다. 따라서 메모리에 저장하도록 구성되는 데이터 구조 (빠른 랜덤 액세스 가능)를 사용할 수있다.

   사전 구현 (주 사전 사용을, 또한 해시 세트 개체 및 ZSET 객체 스킵리스트와 함께), 레디 스 누구 액세스 복잡도 O 인 별도 체인 해시 테이블을 사용하는 (1 + N / K) 여기서, 해당 항목의 개수 및 버킷 수 케이.

   레디 스 버킷의 수는 실제로 N / k는 낮게 유지되도록 항목의 수와 함께 성장 확인합니다. 이 다시 해싱 활동은 백그라운드에서 점진적으로 이루어집니다. 항목 수가 크게되면 복잡도는 가까운 O (1) (상각)이다.

   성능상의 이유로 임의 I / O 수를 최소화하면서 다른 상점 (예를 들어 카산드라) 디스크에 데이터를 저장하도록 설계되어 있습니다. 이 데이터의 지역성을 적용하지 않기 때문에 해시 테이블은, 이것에 대한 좋은 데이터 구조되지 않습니다 (아주 잘 캐시 버퍼에서 도움이되지 않습니다). 디스크 기반 저장은 일반적으로 B-나무가 변형 사용 (대부분의 RDBMS) 정도 병합 (LSM) 나무를 O (로그 n)의 복잡도가 (카산드라), 변종 로그 구조.

   모든 데이터가 메모리에 적합해야합니다 그래서 그래, 제약은 레디 스 제공에 많은 작업을위한 O (1), 그러나이있다. 여기에 마술은 존재하지 않는다.

from https://stackoverflow.com/questions/15216897/how-does-redis-claim-o1-time-for-key-lookup by cc-by-sa and MIT license