Index

Index가 왜 필요한가요?

테이블의 모든 데이터를 순차적으로 검색하는 것은 시간이 오래걸리기 때문입니다.

조건을 만족하는 튜플을 빠르게 조회하기 위해

[꼬꼬무1] select의 성능을 높일 수 있는 방법은 뭐가 있을까요?

가장 대표적인 방법으로는 Index 생성, 조건절 최적화, join 최적화, 필요한 컬럼만 추출 등이 있습니다.

[꼬꼬무2] index의 내부동작은 어떻게 동작하나요?

내부 구현 알고리즘에 따라 다르지만 균형 바이너리 서치 트리를 사용하는 경우 key의 크기 기준으로 나보다 작으면 왼쪽 서브트리 탐색, 나보다 크면 오른쪽 서브트리를 탐색해 O(log n)시간에 탐색합니다.

[꼬꼬무3] index를 많이 생성하면 안되나요?

인덱스 생성자체가 추가적인 메모리를 사용하고 insert, delete 작업 시에도 추가적인 연산이 필요하기 때문에 상황에 따라 적절하게 사용하는 것이 좋습니다.

index를 어느 column에 사용하는 것이 좋을까요? ⭐⭐⭐⭐

자주 조회하고 수정빈도가 적으며 값의 범위가 넓은 컬럼을 선택하는 것이 좋습니다.

[꼬꼬무1] index를 쓰면 성능이 좋아지니까 모든 컬럼에 인덱스를 사용하면 성능이 더 좋겠네요?

수정빈도가 적으며 값의 범위가 넓은 컬럼에만 사용하는 것이 좋습니다.

 

Index를 생성하게 되면 INSERT, DELETE, UPDATE 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생합니다. INSERT 의 경우 INDEX에 대한 데이터도 추가해야 하므로 그만큼 성능에 손실이 따릅니다. DELETE 의 경우 Index에 존재하는 값은 삭제하지 않고 사용 안함 표시만 남기기 때문에 삽입, 삭제 빈도가 많아지면 Index 테이블이 엄청 늘어나 오히려 성능저하 현상이 발생할 수 있습니다.

 

그리고 값의 범위가 좁은 경우도 인덱스를 통해 범위를 좁히지 못해 오히려 성능 저하 현상이 발생합니다.

 

• delete시 삭제 하지 않는 이유

tree 자체를 balance 하게 변경하는 것이 더 비용이 많이 들기 때문이다

 

[꼬꼬무2] 우리 회사의 고객 DB에서 성별 column에 index를 걸어주는게 좋을까요?

성별같은 경우도 값의 범위가 작기 때문에 index를 걸어주는게 적절하지 않다.

[꼬꼬무3] true 또는 false 값을 갖는 column에서, true 1%, false 99%의 비율로 구성된 상황에서는 index를 거는게 좋을까요?

이 경우도 값의 범위가 매우 작기 때문에 index를 걸어주는게 적절하지 않다.

데이터를 검색을 할 때 hash table의 시간복잡도는 O(1)이고 b+tree는 O(logn)으로 더 느린데 왜 index는 hash table이 아니라 b+tree로 구현되나요? ⭐

일반적으로는 해시테이블을 이용한 데이터 접근이 더 빠르지만 SELECT 질의 조건에는 부등호(<>) 연산도 포함이 되기 때문에  등호 연산에 특화된 hash는 적합하지 않습니다.

 

• ORDER BY/GROUP BY 연산의 동작 과정을 인덱스의 존재여부와 연관지어서 설명해 주세요.

ORDER BY: ORDER BY 절의 속성에 대한 인덱스가 있는 경우, 데이터베이스는 인덱스를 활용하여 정렬 작업을 수행합니다. 인덱스는 데이터를 정렬된 상태로 유지하고 있기 때문에 정렬 작업에 대한 비용을 크게 줄일 수 있습니다.

GROUP BY: GROUP BY 절의 속성에 대한 인덱스가 있는 경우, 데이터베이스는 인덱스를 활용하여 그룹화 작업을 수행합니다. 인덱스는 데이터를 그룹화된 상태로 유지하고 있기 때문에 그룹화 작업에 대한 비용을 크게 줄일 수 있습니다.

• 기본키는 인덱스라고 할 수 있을까요? 그렇지 않다면, 인덱스와 기본키는 어떤 차이가 있나요?

일반적인 RDMS에서 PK를 자동으로 Index적용하기 때문에 인덱스라고 할 수 있습니다.

• 그렇다면 외래키는요?

DB에 따라 다르지만 innoDB인 경우 자동으로 Index를 생성한다고 합니다.

 

InnoDB는 MySQL 데이터베이스의 기본적인 스토리지 엔진으로 데이터를 저장, 관리, 검색하는데 사용되는 핵심 기술이다. 대표적으로 트랜잭션 지원, locking, 외래키 지원 등의 기능이 있습니다.

B Tree (balanced tree)

자식 노드가 두개인 이진탐색트리를 일반화한 트리다

B Tree 데이터 삽입

1.  추가는 항상 leaf 노드에 한다.

2. 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.

1 추가 (추가는 항상 leaf 노드에 한다.)

15 추가 (추가는 항상 leaf 노드에 한다.)

2 추가 (노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.)

B 트리 데이터 삭제

삭제 후 최소 key수(Math.ceil(M/2)-1)보다 적어졌다면 재조정한다

1. key 수가 여유있는 형제의 지원을 받는다

2. 1번이 불가능하면 부모의 지원을 받고 형제와 합친다

3. 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.

 

인덱스로 B tree를 사용해야 하는 이유

AVL tree, Red Black tree, B tree 모두 삽입, 삭제, 수정이 O(logN)이지만 인덱스로 B tree를 사용하는 이유에 대해 알아보겠다.

1. 데이터를 찾을 때, 탐색 범위를 더 빠르게 줄일 수 있다.

2. HDD로 부터 데이터를 읽어올 때, block 단위로 읽어오는데 B tree가 block 단위에 대한 저장 공간 활용도가 더 좋다.

B+Tree

B+tree는 B-tree의 확장개념으로, B-tree의 경우, branch 노드에 key와 data를 담을 수 있습니다. 하지만, B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않습니다. 오직 리프 노드에만 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있습니다.

B+tree의 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있습니다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아져 탐색이 빨라집니다

2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되어 모든 노드를 확인해야하는 B-tree에 비해 빠릅니다.

• 그렇다면, B+Tree가 B-Tree에 비해 반드시 좋다고 할 수 있을까요? 그렇지 않다면 어떤 단점이 있을까요?

B+Tree같은 경우 삽입, 삭제 연산이 복잡하기 때문에 수정이 빈번한 데이터베이스인 경우 오버헤드가 발생할 수 있습니다.

• DB에서 RBT를 사용하지 않고, B-Tree/B+Tree를 사용하는 이유가 있을까요?

B-Tree와 B+ 트리는 데이터가 정렬된 상태로 저장되어 있기 때문에 범위 검색과 정렬 연산이 빠릅니다. 레드-블랙 트리는 일반적으로 정렬된 순서를 유지하지 않으므로, 범위 검색과 정렬을 위해 추가적인 작업이 필요할 수 있습니다.

B-Tree와 B+ 트리는 중복된 값을 처리하는 데 효율적입니다. 인덱스 구조에서 중복된 키 값을 다룰 수 있는 방법을 제공하여 데이터 일관성과 효율성을 유지할 수 있습니다. 반면, 레드-블랙 트리는 중복된 값을 처리하기 위해 추가작업이 필요합니다. 

• 오름차순으로 정렬된 인덱스가 있다고 할 때, 내림차순 정렬을 시도할 경우 성능이 어떻게 될까요? B-Tree/B+Tree의 구조를 기반으로 설명해 주세요.

 

• 클러스터링 인덱스란 무엇인가?

테이블 자체가 정렬되는 인덱싱 방법으로

다음과 같은 데이터가 있을 때, 빨간색 컬럼을 클러스트링 인덱스로 지정하면

위 와 같이 테이블 자체가 정렬되면서 인덱스 테이블이 생성되는 것을 의미합니다.

• 인덱스 동작 방식

조건절이 2개이고 index는 그 중 하나만 걸려 있는 경우

a에 대해서는 index를 이용해 빠르게 찾고 b에 대해서는 완전 탐색

 

다음과 같이 인덱스가 걸려 있고

4개의 쿼리가 있을 때, 1,2번은 인덱스의 도움을 받으나

3 같은 경우 인덱스가 team_id로 먼저 정렬한 다음, backnumber로 정렬되어 있어 full-scan과 성능이 유사하고

4번도 team_id를 구할 때는 유용하나 backnumber구할 때는 index가 도움이 되지 않는다. 

• Covering index

다음과 같이 select하려는 attribute가 index안에 다 포함 되어있을 때, 원본 테이블까지 접근 안해도 되는 경우