index 가 뭔지, 동작원리에 대해 설명해보세요(실제 기술면접 질문)

개발지식

우루쾅 2024. 2. 13. 10:16

728x90

SMALL

이전 기술면접을 진행했던 당시 index 의 동작원리에 대해서 질문을 받았는데

대략적적으로 index가 뭔지는 알고 있었지만 상세하게 답변을 못했던 기억있어 확실하게 알기위해! 문서를 작성해봅시다.

인덱스(index)는 데이터베이스에서 검색 속도를 향상시키는데 중요한 역할을 하는 자료구조입니다! 데이터베이스에서는 대량의 데이터를 효율적으로 처리해야하는데, 인덱스는 이를 가능하게끔 합니다.

또한, 데이터베이스 인덱스는 특정 열 또는 컬럼에 대한 정렬된 구조로 데이터를 저장하며, 이를 통해 데이터베이스 시스템은 빠른 검색을 가능하게 하고 특히 WHERE 절에서 자주 사용되는 조건에 따라 데이터의 위치를 빠르게 찾아줍니다.

INDEX 의 종류에는 이진탐색트리(Binary Search Tree), B-tree, B+tree 세가지 종류가 있는데 각각 어떠한 원리로 동작하는지 확인해보겠습니다!

데이터를 저장하고 탐색하기 위한 인덱스 구조입니다.

● 각 노드는 최대 두 개의 자식 노드를 가집니다.

● 왼쪽 자식은 현재 노드보다 작은 값을 가지며, 오른쪽 자식은 큰 값을 가집니다.

● 이진 탐색 트리에서는 데이터를 삽입, 삭제, 검색할 때 평균적으로 O(log n)의 시간 복잡도를 가집니다.

● 하지만, 트리가 균형을 잃어 한쪽으로 치우친 경우 최악의 경우에는 O(n)의 시간 복잡도를 가질 수 있습니다.

데이터베이스 시스템에서 사용되는 인덱스 구조로, 대량의 데이터를 효율적으로 저장하고 탐색하기 위해 고안되었습니다.

● B-tree는 여러 개의 자식을 가지는 다차원 트리입니다.

● 각 노드는 여러 개의 키와 포인터를 가지며, 키는 정렬된 상태를 유지합니다.

● B-tree에서는 각 노드가 일정한 수의 키를 가지는데, 이를 통해 높이를 낯주고 탐색 성능을 향상시킵니다.

● B-tree는 데이터 베이스에서 범위 검색과 같은 연산에 특히 유용합니다.

● B-tree의 시간 복잡도는 평균적으로 O(log n) 입니다.

B-tree의 변형으로, 주로 파일 시스템과 데이터베이스에서 인덱스로 사용됩니다.

- 루트 노드 (Root Node) - 최상위 단 하나의 노드

- 브랜치 노드 (Branch Node) - 중간 노드

- 리프 노드 (Leaf Node) - 최하위 노드

● B-tree와 유사하지만, 내부 노드에는 키만 저장되고, 리프 노드에는 키와 관련된 데이터의 포인터가 저장됩니다.

● 이러한 구조로 인해 B+tree는 범위 검색과 정렬된 결과를 효율적으로 처리할 수 있습니다.

● B+tree 에서는 데이터를 순차적으로 접근할 수 있는 순차 접근 포인터를 가지고 있습니다.

● B+tree 의 시간 복잡도 또한 평균적으로 O(log n) 입니다.

출처

GPT-4

[오라클/SQL] CREATE INDEX : 인덱스 생성 방법, 인덱스 만들기 (B-TREE, BITMAP, UNIQUE, ...) https://m.blog.naver.com/regenesis90/222208047475

728x90

LIST