[DB] 데이터베이스 인덱스(Index)

💡 데이터베이스 인덱스, 많이 들어만 봤지 정리 좀 하자 !

 노션에서 보기

 

🔖 인덱스란 ?

• Index 란, RDBMS에서 검색 속도를 높이기 위한 기술
• TABLE 의 컬럼을 **색인화(따로 파일로 저장)**하여→ **검색 속도를 향상**시킨다.
• → 검색시 해당 테이블의 레코드를 Full Scan 하는 것이 아닌, **색인화 되어있는 INDEX 파일을 검색**하여
• 인덱스 자료구조로는 Hash Table, B-Tree 에서 파생된 B+Tree

 

❓인덱스 필요성

• 데이터를 디스크로부터 가져올 때 자주 사용하는 것을 메모리에 저장하여 빠른 속도로 조회/검색 필요
  • 기존에 item_info 테이블에 존재하는 total row = 2846 개이며, 위의 쿼리를 실행한 경우 전체 row 개수에 해당하는 2846 개의 row 가 조회된 것을 확인할 수 있다.데이터가 메모리에 없다면 테이블 내에서 전체 스캔을 통해 조회해야 함(Full Table Scan)
    • **Full Scan, Table Scan**
      • SQL 서버에서는 데이터 레코드가 내부적으로 아무런 순서없이 저장된다.
      • 이때 데이터 저장 영역을 Heap 이라고 하며,→ Full Scan, Table Scan
      • Heap 에서는 인덱스가 없는 테이블의 데이터를 찾을 때 전체 데이터 페이지의 처음 레코드부터 ~ 끝 페이지의 마지막 레코드까지 모두 조회하여 검색 조건과 비교 한다
      • 많은 테이블에서 데이터 일부만 찾을 때 Full Scan 을 할 경우, 처리 성능이 떨어진다.
      • 대용량 데이터에 비효율적이므로 인덱스를 통해 데이터를 관리하여 SELECT 검색 성능을 높이도록 한다.
    • 아래와 같이 Explain 쿼리를 실행하는 경우, 검색된 ROW 는 아래에 나타나는 것을 확인할 수 있다.

 

 

• 인덱스는 **메모리**에 저장

 

📑 인덱스의 자료구조와 원리

 

🗃️ 해시 테이블(Hash Table)

 

 

• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로, 빠른 데이터 검색에 유용
• 해시 테이블은 Key 값을 이용해 고유한 Index 를 생성해 → 그 Index 에 저장된 값을 꺼내오는 구조
• 해시 테이블 기반의 DB 인덱스는 (데이터 = 컬럼의 값, 데이터 위치) 를 **(Key, Value)**로 사용
  • 컬럼의 값으로 해시 함수를 거쳐 생성된 해시를 통해 인덱스 구현 → 버킷 배열의 인덱스
  • 내부적으로 **배열(버킷)**을 사용하여 데이터를 저장
  • buckets[Index] = 데이터
• 해시 테이블의 평균 시간 복잡도 = O(1)

 

해시 인덱스 장점

• 해시 테이블의 시간복잡도 = O(1)
• → 매우 빠른 검색 가능

 

해시 인덱스 단점

• 검색을 위한 해시 인덱스에서는, 충돌이 많이 발생할수록 검색 효율 저하
  • 충돌 : 입력 값이 다르지만, 결과 값이 같은 경우, 즉 입력 값은 다르지만 해시 값이 같은 경우
  • 해시 함수 결과 값의 범위가 좁으면 → 필요한 버킷 수가 감소 → But, 충돌이 많이 발생
  • 해시 함수 결과 값의 범위가 넓으면 → 필요한 버킷 수가 증가 → But, 충돌 발생 감소
  • 데이터 충돌이 발생한 경우, Chaining 에 연결된 리스트들까지 검색해야 하므로 O(N) 까지 시간복잡도 증가 가능
  • 해시 테이블의 충돌에 의한 문제 해결 - 분리 연결법(Separate Chaining) & 개방 주소법(Open Addressing)
    • 분리 연결법 : 동일한 버킷의 데이터에 대해 자료구조를 활용해 “추가 메모리”를 사용해 → 다음 데이터의 주소를 저장하는 방법  

 

분리 연결법

 

 

               

• 개방 주소법 : “비어있는 해시 테이블의 공간”을 활용하는 방법
  • Linear Probing : 현재 버킷 index 로부터 고정폭 만큼씩 이동해 → 차례대로 검색해 비어있는 버킷에 데이터 저장
  • Quadratic Probing : 해시의 저장순서 폭을 제곱으로 저장하는 방식
    • Ex) 처음 충돌이 발생한 경우, 1만큼 이동 → 그 다음 충돌이발생한 경우 2^2 → 2^3 만큼씩 이동
  • Double Hashing Probing : 해시된 값을 한 번 더 해싱하여 → 해시의 규칙성을 없애버리는 방식
    • 해시된 값을 한 번 더 해싱해 새로운 값을 할당 → 더 많은 연산 필요

 

Double Hashing 전략

 

• Open Addressing 에서 데이터 삭제시 → 삭제된 공간은 Dummy Space로 활용
  • Hash Table을 재정리 하는 작업 필요

 

• 해시가 등호(=) 연산에만 특화되어 있음
  • 해시 함수의 값이 1이라도 달라지면 → 다른 해시 값을 생성
  • 부등호 연산(>, <) 이 자주 사용되는 DB 검색에는 해시 테이블이 적합하지 않음
  • Ex) “나는 ~” 으로 시작하는 모든 데이터를 검색하기 위한 쿼리문 → 인덱스의 혜택을 받지 못함

 

해시 테이블(Hash Table) Vs 해시맵(HashMap)

• 두 자료구조의 차이는 “동기화 지원 여부”
• 해시 테이블 : 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황에서 사용
  • 해시테이블의 put 에는 synchronized 키워드가 붙음
  • 병렬 프로그래밍에서 동기화 지원
  • 해당 함수를 처리하는 시간이 조금 지연됨
• 해시맵 : 병렬 처리를 하지 않거나, 자원의 동기화를 고려하지 않는 상황에 사용

 

🌲 B-Tree

 

B-Tree 란?

 

 

• 이진트리와 유사하지만, 이진트리와 달리 자식 노드가 2개 이상 가능한 구조
  • 가장 상단의 노드 = 루트 노드(Root Node)
  • 중간 노드 = 브랜티 노드(Branch Node)
  • 가장 아래 노드 = 리프 노드(Leaf Node)
  • 수직적 탐색과 수평적 탐색으로 이루어짐
    • 수직적 탐색 : 조건을 만족하는 첫 번째 레코드를 찾아감
    • 수평적 탐색 : 리프 노드에서 조건을 만족하는 노드를 찾아나감

B-Tree

 

• 이진 검색 트리처럼 각 Key 의 왼쪽 자식은 항상 Key 보다 작은 값을 / 오른쪽 자식은 Key 보다 큰 값을 가짐
• B-Tree 의 Key-Value 값은 항상 Key 를 기준으로 오름차순 정렬
  • 부등호 연산에 대해 해시 테이블보다 효율적인 탐색 가능
• 평균 시간 복잡도 = O(logN)
• Inno DB Storage Engine : 디스크에 데이터를 저장하는 가장 기본단위를 페이지로 관리
  • 페이지 : 디스크의 읽기, 쓰기 최소 단위
  • 인덱스도 페이지 단위로 관리
• Range Scan
  • Leaf 블록에서 스캔 시작점을 찾아 → 스캔을 하다가, 찾고자 하는 데이터를 찾는 경우 Scan 을 종료
  • Full Scan에 비해 효율적임

 

B-Tree 특징

• 균형트리
  • “균형트리"란, 루트로부터 리프 도드까지 거릭 ㅏ일정한 트리 구조
  • 트리 중에서 성능이 안정화 되어있음
• B-Tree 처음 생성 당시 - 균형 트리이지만,
• 테이블 갱신(INSERT/UPDATE/DELETE)의 반복을 통해 서서히 균형이 깨지고 성능이 악화될 수 있다.

→ 어느 정도 자동으로 균형을 회복하는 기능도 있지만,

→ 갱신 빈도가 높은 테이블에 작성되는 인덱스는 - 인덱스 재구성을 통해 트리의 균형 회복 필요

 

Key 검색 과정

• 이진 검색 트리의 성질을 이용해 하향식으로 검색 수행
  • 이진 검색 트리 : 각 Key 들의 왼쪽 자식은 항상 Key 보다 작은 값을, 오른쪽은 큰 값을 가짐

 

B-Tree 에서 Key 검색 과정

 

B-Tree Key 검색 과정

 

B-Tree 인덱스 장점

• 균일성
  • 어떤 값에 대해서도 같은 시간(=O(logN))에 결과를 얻을 수 있다
• 데이터 양에 비래해 처리 시간 속도 상승
  • 풀 스캔 : 테이블 크기에 비례하는 형태로 처리 시간 증가
  • 인덱스 : 실행 시간 저하는 보통 원만한 곡선을 이룸

 

 

B-Tree 인덱스 단점

• Index 가 적용된 테이블에 데이터 갱신(INSERT/UPDATE/DELETE) 이 반복 → 트리의 균형이 깨지며 성능 악화
• DB Index 컬럼은 부등호를 이용한 ‘순차 검색 연산' 이 자주 발생
  • B-Tree 가 오름차순 정렬되어 있어 → 해시 테이블 보다 부등호를 이용한 검색 연산 성능이 좋지만,
  • 순차 검색의 경우 “중위 순회" 를 하기 때문에 효율이 좋지 않음
  
  
  • 위의 예시에서 노드 6을 찾기 위해
    • 7 > 3 > 8 > 1 > 9 > 4 > 10 > 0 > 11 > 5 > 2 > 6 순서로 조회해야 함

 

🌳 B+Tree

 

B+Tree 란?

 

B+Tree

 

• **B+Tree 란, Leaf Node 만 (인덱스 + 데이터)**를 함께 가지고 있고,
• 나머지 노드(Inner Node) 들은 데이터를 위한 인덱스(Key) 만을 갖는다.
  • B-Tree 의 경우, Internal(Inner, Brandch) Node 에 Key 와 Data 를 모두 담을 수 있다.
• 리프 노드끼리는 Linked List 로 연결되어 있다.
  • 즉, 리프 노드끼리는 Linked List 로 서로를 참조하고 있어,
  • 부등호를 이용한 순차 검색 연산 시 중위 순회를 통해 많은 노드를 방문해야 하는 B-Tree 에 비해 B+Tree 는 리프 노드를 저장한 Linked List 를 한 번만 탐색하면 된다.

 

B+Tree 인덱스 장점

• 리프 노드를 제외하고 데이터를 담아두지 않음→ 더 많은 Key 수용 가능→ Cache Hit 향상 가능
• → 하나의 노드에 더 많은 Key 를 담을 수 있어, 트리의 높이를 낮출 수 있음
• → 메모리 확보 가능
• Full Scan 시 리프 노드에 데이터가 모두 있어 → 한 번의 선형 탐색만 하면 되므로, B-Tree 에 비해 빠름
  • B-Tree 의 경우 모든 노드를 확인해야 함

 

B+Tree 인덱스 단점

• B-Tree 의 경우 Best Case 에 대해서는 리프노드까지 가지 않아도 검색(조회)가 가능하지만, B+Tree 의 경우 리프 노드까지 가야 데이터를 조회할 수 있다

 

B-Tree Vs B+Tree 인덱스

 

🚦인덱스 종류

• 인덱스는 크게 Clustered 와 NonClustered 인덱스로 나뉨

 

Clustered Index

• Clustered Index 는 물리적 정렬로 DB에 데이터를 입력 시 Clustered 인덱스를 기준으로 입력이 된다.
• 한 테이블에 오직 하나만 존재 가능
• → 테이블 내에서 ORDER BY 를 하지 않아도, 데이터가 Clustered 인덱스에 따라 정렬이 되어 있는 것을 확인할 수 있다.
• 물리적으로 정렬되어 있어 → 가장 빠른 처리 가능
  • Auto Increment

 

NonClustered Index

• NonClustered Index 는 Clustered Index 와는 달리, 중복된 값을 가지면 → 한 테이블에 여러 개를 생성할 수 있다.
• 자동 정렬되지 않고, Index 를 생성할 때는 Clustered 가 되어있을 때 Index Scan 이 유리하다.
• 약한 참조 관계 → 굳이 정렬을 하지 않아도 됨

 

🕖 인덱스를 언제 사용할까?

• SELECT / INSERT / UPDATE / DELETE 중 SELECT 를 수행할 때는 효과적이지만, 다른 DML을 사용하는 경우 성능 저하 발생
  • INSERT 는 왜 성능을 저하시키는가?
    • INSERT 는 정렬이 된 상태로 데이터가 저장이 되어야 하기 떄문
    • 어느 자리에 INSERT 를 해야하는지를 찾아 → 저장하고 → 원래 위치하는 데이터를 뒤로 밀어주어야 함
    • 만약, 저장할 페이지, 블록이 꽉 차게 되는 경우 다음 페이지로 옮겨야 하며 처리해야 하는 작업이 더 많아지게 됨
    • 인덱스는 테이블과 별도의 객체이므로, 테이블에도 삽입을 해주어야 함
  • DELETE 는 왜 성능을 저하시키는가?
    • DELETE 는 데이터를 실제로 지우는 것이 아닌, 인덱스 내에 ‘사용 안 함’ 표시 처리
    • 공간 낭비 존재
  • UPDATE 는 왜 성능을 저하시키는가?
    • 인덱스에는 UPDATE 개념이 없음
    • UPDATE 가 발생할 경우, DELETE 수행 후 → INSERT 처리
    • 작업 부하 존재
• SELECT FROM WHERE 과 같이 조건절에서 사용하는 것이 효과적
• 특정 열을 고려 대상에서 빨리 제거하기 위해
• **조인(JOIN)**을 실행할 때 다른 테이블에서 열을 추출하기 위해
• 특정하게 인덱스된 컬럼을 위한 MIN(), MAX() 값을 찾기 위해
• 사용할 수 있는 키의 최 좌측 접두사(leftmost prefix)를 통해 정렬 및 그룹화를 위해
• 데이터 열을 참조하지 않는 상태로, 값을 추출하기 위해 쿼리를 최적화 하는 경우

 

🔍 인덱스 Column 설정 기준

• Cardinality(기수성)가 높은 것
  • 고유한 값의 수가 많다는 것
  • 아래 예시에서, 주민번호의 카디널리티 > 성별 카디널리티
  • 카디널리티가 높은 컬럼의 경우, Index 를 통해 더 많은 데이터를 필터링 할 수 있기 때문

 

 

카디널리티

 

카디널리티 개념

• **전체 행에 대한 특정 컬럼의 중복 수치**를 나타내는 지표
• 중복도가 ‘낮으면' → 카디널리가 ‘높다’
• 중복도가 ‘높으면' → 카디널리티가 **‘낮다’**

 

셀 수 있는 카디널리티와 셀 수 없는 카디널리티

• 셀 수 있는 카디널리티
  • 성별 : 남/여 → 카디널리티 = 2
  • 요일 : 월 ~ 일 → 카디널리티 = 7
• 셀 수 없는 카디널리티
  • 주민등록번호 : 유니크한 값 → 현재 행을 count 한 값

 

상대적인 개념의 카디널리티

• 카디널리티가 높다/낮다는 비교 대상이 존재하고, 그 대상에 비해 높다/낮다라고 표현하므로 상대적인 것
  • Ex) 요일의 카디널리티 = 7→ 요일 > 성별, 요일 < 주민등록번호
  • 성별의 카디널리티 = 2
• Distinct 한 값이 높으면 중복도가 낮다 / 카디널리티가 높다

 

멀티 인덱싱 전략

• 인덱스를 걸 때에는, 최대한 많은 데이터가 걸러져야 full scan 을 피할 수 있다.
• 카디널리티가 높은 컬럼을 우선순위에 두는 것이 인덱싱 전략에 유리
  • Ex) 주민등록번호 → 성별 순으로 인덱싱

 

인덱스 장점

• 키 값을 통해 테이블에서 검색 및 정렬 속도 향상
• 그룹화 작업 속도 향상
• 인덱스 사용 시 테이블 행의 고유성 강화 가능
• 테이블의 기본키 = 자동으로 인덱스가 됨

 

인덱스 단점

• Index 생성 시 .mdb 파일의 크기가 증가
• 한 페이지를 동시에 수정할 수 있는 병행성 저하
• Index 된 필드에서 데이터를 업데이트 하거나, 레코드 추가 및 삭제 시 성능저하
• 데이터 변경 작업이 자주 발생하는 경우, Index를 재작성해야 하므로, 성능에 영향을 미침
• Index 생성 시 시간 소요
• Index 가 DB 공간을 차지 → 추가적인 공간(DB의 10% 내외 추가 공간)필요

 

참고자료

• 참고1
• 참고2
• 참고3
• 참고4
• 참고5
• 참고6
• 참고7
  • • •  

• • • •