Redis가 지원하는 자료구조 중 string을 다룬다고 가정
MySQL은 단일 테이블에 대한 오퍼레이션이며 index는 hash 인덱스가 아니라 가정
MySQL vs Redis
| Op | MySQL에서 인덱스 X | MySQL에서 인덱스 O | Redis |
|---|---|---|---|
| 검색 | O(N) | O(log N) | O(1) |
| 삽입 | O(1) | O(log N) | O(1) |
| 수정 | O(1) | O(log N) | O(1) |
| 삭제 | O(1) | O(log N) | O(1) |
수정, 삭제 대상 검색에 대한 시간복잡도는 제외
MySQL(InnoDB) - With the exception of spatial indexes, InnoDB indexes are B-tree data structures.
Redis - Redis use separate chaining hash tables, whose access complexity is O(1+n/k) where n is the number of items and k the number of buckets.
Reference
https://redis.io/docs/data-types/strings/
https://dev.mysql.com/doc/refman/8.0/en/innodb-physical-structure.html
https://github.com/ZhenningLang/redis-command-complexity-cheatsheet
https://stackoverflow.com/questions/15216897/how-does-redis-claim-o1-time-for-key-lookup
https://www.geeksforgeeks.org/sql-query-complexity/
https://yurimkoo.github.io/db/2020/03/14/db-index.html
Backend Developer