인덱스 개념 다시 보기
-
DB에서 인덱스란 추가적인 저장 공간을 사용해서 테이블 검색 속도를 향상시키기 위한 자료구조 입니다.
-
인덱스는 SELECT 쿼리의 WHERE 절에 사용될 컬럼에 대한 조회 성능을 개선할 때 사용됩니다.
- 인덱스가 없으면 데이터를 탐색할 때 Full Table Scan을 하는데, 이는 가장 느린 테이블 스캔 방식입니다.
인덱스 알고리즘 종류
B-Tree 인덱스 알고리즘
-
가장 일반적으로 먼저 도입된 알고리즘
-
탐색 시간복잡도: O(logN)
B+Tree 인덱스 알고리즘
-
B-Tree를 개선시킨 자료구조
-
MySQL 등 많은 DBMS에서 사용하는 알고리즘
-
탐색 시간복잡도: O(logN)
Hash Table 인덱스 알고리즘
-
Key를 사용하여 원하는 자료에 빠르게 접근하는 자료구조
-
부등호 연산에 부적합, 범위 검색 불가 등의 이유로 많은 DBMS에서 인덱싱 알고리즘으로 사용되지 않는다.
-
탐색 시간복잡도: O(1)
ref.
https://github.com/Seongwon97/tech-interview/blob/main/Q&A/Database_Q&A.md
https://hudi.blog/db-index-and-indexing-algorithms/
