[기술면접 대비] Database 3 - Index, Replication

Index & Cluster Index, Non-Clustered Index

👉 Index란?

Index 는 DB Table에 대한 검색 성능의 속도를 높여주는 자료 구조

 

👉 Index 특징

• 필드에 Index 설정시 Index Table이 별도의 메모리 공간에 물리 주소와 함께 생성됨 (추가 메모리 사용 발생)
• Index Table에 쿼리 요청시 해당 주소로 바로 연결하여 결과 값을 조회
• index는 테이블은 특정 key로 찾으며, 해당 key 값은 B-Tree 형태로 평소 저장되어 빠르게 탐색 가능

 

👉 Clustered Index, Non-Clustered index 란?

• Clustered Index : 특정 컬럼을 index로 설정하여 index table에 정렬된 상태로 유지하는 것 (ex. id를 clustered index로 지정하여 id 기준 데이터 정렬된 상태로 저장)
• Non-Clustered index : 데이터가 테이블에 정렬 되지 않고 저장된 경우

 

👉 Clustered Index 특징

• ndex Table은 항상 정렬된 상태로 유지됨
• Primary Key로 제약조건 설정시, Clustered Index로 자동 생성 
• 테이블 당 1개만 정의 but, 여러 필드로도 가능
• 데이터 삽입/수정/삭제시 재 정렬로 인해 많은 비용듬 (중간에 행 추가시 데이터 한칸씩 옮겨야 함)

 

👉 Clustered Index 사용하면 좋은 경우

• 테이블의 index로 설정한 필드가 자주 업데이트 되지 않는 경우
• 항상 특정 필드의 정렬된 데이터 반환 필요시
• 읽기 작업이 많은 필드 - 데이터를 찾는데 추가적인 스텝을 거치지 않음 (Leaf Level과 Data Page가 같이 있음)

 

👉 Non-Clustered index 특징

• 데이터를 별도의 장소하여, id 값과 주소로 실제 데이터 연결하여 찾음
• 한 Table 에 여러개 생성 가능

 

👉 Non-Clustered Index 사용하면 좋은 경우

• 데이터가 자주 업데이트 될 때
• Where 절이나 Join 절과 같이 조건문을 활용하여 테이블 필터링시

 

Index 장단점

👉 Index 장단점

장점 : 테이블 조회 성능 향상 / 정렬 되어 있어FullScan 하지 않아도 되어 탐색시 비용이 적게듬

단점

• 인덱스를 관리하기 위한 추가 DB 공간 필요 (index table)
• INSERT, UPDATE 등 TABLE 수정 소요 발생시 INDEX TABLE이 재 정렬되어야 함
• 인덱스 관리를 위한 추가 작업 필요 (DML에 비교적 취약)

 

👉 Index 가 INSERT, UPDATE, DELETE에서 성능 저하되는 이유

index Table이 수정되서 재 정렬 되어야 하므로

 

👉 Index가 효율적인 이유는?

• 전체를 Full Table Scan 하지 않고, Index Table에서 가져오기 때문
• Index 알고리즘은 주로 모든 요소에 효율적으로 접근 할 수 있는 균형 트리 구조와 트리 깊이의 대수 확장성 때문
• 대수확장성 : 트리 깊이가 리프 노드 수에 비해 느리게 성장하는 것 (ex. depth 1 추가시 node 당 4개 index 추가)

 

👉 index를 쓰면 좋은/안 좋은 케이스

좋은 곳

• 탐색 성능을 효율적으로 개선할 수 있는 규모가 큰 Table (ex. 검색, 정렬 등)
• 탐색 성능을 효율적으로 개선할 수 있는 JOIN, WHERE, ORDER BY 가 있는 경우
• (django) 문서 왈 filter, exclude, order_by 등 조회 관련하여 자주 사용되는 컬럼에 db_index를 사용 권장

 

안 좋은 곳 : 데이터의 변경이 잦은 컬럼 (자주 발생시 Index 관리에 대한 오버헤드가 커짐)

 

👉 index 만드는 법 (DBMS에서 INDEX 관리하는 방법)

• MySQL : B-Tree / Primary key 설정 / Clustered Index / Secondary Index 가능
• MongoDB : ObjectId 필드 자동 생성

 

Index 자료구조

👉 트리 자료구조 구성

이진트리 기반 : 탐색 성능을 높이기 위해 트리가 한쪽으로 치우치지 않고 Balanced 있게 저장됨 (+정렬된 상태) 

이진트리 탐색 속도 : 항상 정렬된 상태로 유지 검색 시간 복잡도 O(log(N))

트리 종류 : B-Tree, B+Tree

시간 복잡도 : 읽기 O(1) - 정렬됬으므로, 검색 O(log(N)), 삽입, 삭제 O(N)

 

👉 B-Tree vs B+Tree

데이터 저장 : left node, branch node (중간노드) vs only left node

트리의 높이 : 높음 vs 낮음

검색 속도 : 모든 노드 탐색 vs left node에서 선형 탐색

링크드 리스트 : 없음 vs 있음

검색 노드 구성 : 자주 접근 되는 노드를 root node 가까이 배치 가능 vs left node에만 배치

 

B-Tree & B+ Tree 이미지 원본 링크 (https://rebro.kr/169?category=484170)

 

조회 성능이 빠르지만, 추가적인 DB 공간이 필요하고, 

정렬된 배열은 읽기에 O(1), (이진) 검색에 O(logN)이 걸린다. 하지만 삽입과 삭제가 상대적으로 느리다. 평균 시나리오에서 N/2 단계, 즉 O(N)

 

Index와 카디널리티 관계, 기타

👉 Cardinality(카디널리티) 란?

카디널리티 : 데이터의 중복 정도에 따른 상대적인 지표

ex) 주민등록번호는 중복도가 낮아 카디널리티가 높다

ex) 이름은 중복도가 높아 카디널리티가 낮다

 

👉 Index 적용시 Cardinality(카디널리티) 를 어떻게 판단해야 하는가?

Index 적용시, 카디널리티가 높은 컬럼(=중복도가 낮은 컬럼)에 걸어야, Filtering시 많은 데이터가 걸러져 유리함 (인덱스를 3개를 걸었으면 앞에서 많이 걸러줘야  성능이 더 좋음)

 

👉 기타 정리 링크

https://yubi5050.tistory.com/137

[DB] Index란?

 

 

DB Scale-up, Scale-out

👉 RDB Scale-up과 Scale-out 방법에 대해 설명하시오 

• Scale-up : Disk 용량을 높인다거나, 서버 장비를 Upgrade
• Scale-out : 이중화, Replication, Master-slave 구조 차용하여 읽기 서비스만 분리

 

Clustering, Sharding, Replication

👉 Clustering이란? 사용이유는? (DB 서버가 죽는 것에 대한 고민)

목표 : 서버를 여러개 만들어 DB SERVER가 죽는 것을 방지하자

종류

• 하나의 큰 STORAGE 안에 2 ACTIVE SERVER => 처리 속도는 더 빠르지만 병목현상 있을 수 있음
• 하나의 큰 STORAGE 안에 ACTIVE-STANDBY => 하나는 대기 상태로 두어 병목현상 X

 

👉 Replication이란? 사용이유는? (DB 손실에 대한 고민)

목표 : 실제 데이터가 저장되는 저장소도 복제하여, 저장된 데이터 손실을 방지하자

종류 : MASTER-SLAVE 구조

특징

• MASTER-SLAVE 구조로 MASTER로 들어온 데이터를 SLAVE로 동기화하여 데이터를 백업
• MASTER는 수정, 삽입, 삭제 역할
• SLAVE는 조회용으로 사용

 

👉 Sharding이란? 사용이유는? (DB 검색 효율에 대한 고민)

목표 : DB 테이블을 나누어 데이터가 너무 많아서 검색이 느린것을 해결해보자

종류 : hash sharding (id%db_num) / dynamic sharding / entity group

특징

• 나눠지는 DB 각각을 SHARD라고 하며, SHARD KEY에 따라 SHARD를 선택함
• SHARD KEY 결정 방식에 따라 SHARDING 방법이 나뉨
• 아래 종류 1과 종류 2는 nosql 저장방식에 더 어울리고, 종류 3은 rdb에 좀더 어울림

 

👉 Sharding의 주요 고려사항은?

• 분산되는 DB DATA를 어떻게 잘 분산 저장할 것인가
• 분산되는 DB DATA를 어떻게 잘 읽을 것인가

 

👉 Sharding의 주요 방법들 설명 (hash sharding / dynamic sharding)

1. hash sharding (id%4)

• 4는 shard 갯수 (저장소 갯수) 
• 최초 구현이 간단 but. Shard 확장시 hashing 함수가 달라져 기존 저장된 데이터의 정합성이 깨짐
• 공간에 대한 효율을 고려 하지 않는다.

 

2. dynamic sharding

• locator service를 두어 id range에 따라서 sharding 하는 방식
• 확장에 유연하지만, locator service를 거쳐야 shard가 정해지므로 의존적임

 

3. entity group

• shard 각각 마다 관련된 rdb table row들을 모아두는 방식
• 단일 shard 내에선 쿼리가 효율적이지만, 데이터간 강한 응집도를 가짐
• 단점은 다른 shard의 entity와 연관이 되는 쿼리의 경우 비효율적임