자료구조 in DB 인덱스

RDBMS의 인덱스란? 인덱스란 DB 테이블에서 특정 데이터에 대한 검색 작업을 수행할 때, 검색 성능을 높이기 위해 사용되는 도구이다. 만약 데이터 N개가 존재하는 테이블에서 특정 칼럼의 값이 X인 데이터를 찾기 위해서는, 전체 테이블을 모두 확인해야 하며 O(N)의 시간복잡도를 갖는다. 이를 Full table scan이라고 하는데, 하나의 데이터를 위해 매번 O(N)이 걸리는 것은 상당히 비효율적이다. 이러한 문제를 해결하기 위한 것이 바로 인덱스이다. 주로 쓰이는 B+Tree 자료구조를 통한 인덱스를 이용 시 위와 동일한 조건에서 O(logN)의 향상된 시간복잡도를 갖는다. 인덱스에 이용되는 자료구조 1. Hash Table 해시 테이블은 Key - Value 자료구조이다. 따라서 특정 데이터의 ..

2023.02.11