/
/

면접을 위한 CS 전공지식 노트 - 인덱스/조인의 종류

인덱스, 조인의 종류
면접을 위한 CS 전공지식 노트인덱스조인의 종류
avatar
케요네즈
2025.05.29
·
18 min read
6492

인덱스 (Index)

인덱스는 데이터베이스 테이블에서 원하는 데이터를 빠르게 찾을 수 있도록 돕는 장치입니다. 이는 책의 마지막 장에 있는 '찾아보기'와 유사한 역할을 하여, 본문 전체를 탐색하지 않고도 특정 항목을 신속하게 찾을 수 있게 합니다.

B-트리

인덱스는 일반적으로 B-트리라는 자료 구조로 구현됩니다. B-트리는 루트 노드(Root Node), 리프 노드(Leaf Node), 그리고 그 사이의 브랜치 노드(Branch Node)로 구성됩니다. 데이터 탐색은 최상위 루트 노드에서 시작하여 브랜치 노드를 거쳐 리프 노드까지 순차적으로 진행됩니다.

인덱스의 효율성 및 대수 확장성

  • 인덱스가 효율적인 주된 이유는 모든 요소에 효율적인 단계를 거쳐 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수 확장성 때문입니다.

  • 대수 확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 증가하는 특성을 의미합니다. 일반적으로 인덱스의 깊이가 하나씩 증가할 때마다 최대 인덱스 항목 수는 약 4배씩 증가하는 경향을 보입니다.

인덱스 생성 방법

인덱스를 생성하는 구체적인 방법은 데이터베이스 시스템마다 차이가 있으며, 여기서는 MySQL과 MongoDB를 기준으로 설명합니다.

DB 종류

인덱스

특징

MySQL

클러스터형 인덱스 (Clustered Index)

  • 테이블당 하나만 설정할 수 있습니다.

  • PRIMARY KEY 옵션으로 기본키를 생성하면 자동으로 클러스터형 인덱스가 됩니다.

  • 기본키가 아닌 컬럼에 UNIQUE NOT NULL 옵션을 지정하여 클러스터형 인덱스를 만들 수도 있습니다.

  • 단일 인덱스만 필요할 경우, 세컨더리 인덱스보다 클러스터형 인덱스가 일반적으로 성능이 더 좋습니다.

세컨더리 인덱스 (Secondary Index)

  • CREATE INDEX ... 명령어를 사용하여 생성합니다.

  • 보조 인덱스로, 여러 필드를 기반으로 하는 쿼리가 빈번할 때 생성하는 것이 유리합니다.

MongoDB

기본키 인덱스

  • 도큐먼트를 생성하면 자동으로 _id 필드에 ObjectID가 할당되며, 이 _id 필드가 기본키로 설정되어 인덱싱됩니다.

복합 인덱

  • 기본키 외에 추가적으로 세컨더리키를 설정하여, 기본키와 세컨더리키를 함께 사용하는 복합 인덱스를 구성할 수 있습니다.

인덱스 최적화 기법

인덱스 최적화 기법은 데이터베이스마다 세부적인 차이가 있을 수 있지만, 기본적인 원리는 유사합니다. 여기서는 MongoDB를 기준으로 설명하며, 이 원칙들은 다른 데이터베이스에도 적용될 수 있습니다.

  1. 인덱스는 비용이다:

    • 이중 탐색: 인덱스를 사용하면 먼저 인덱스 리스트를 탐색하고, 그 결과를 바탕으로 실제 컬렉션(테이블)을 탐색하게 되어 두 번의 탐색 과정과 관련된 읽기 비용이 발생합니다.

    • 유지보수 비용: 컬렉션의 데이터가 수정(삽입, 삭제, 갱신)될 때마다 인덱스도 함께 수정되어야 합니다. 이 과정에서 B-트리의 균형을 맞추고 데이터를 효율적으로 분산시키는 데 추가적인 비용이 소모됩니다.

    • 무분별한 설정 지양: 따라서 쿼리에 사용되는 모든 필드에 무작정 인덱스를 설정하는 것은 비효율적입니다.

    • 데이터 조회량 고려: 컬렉션에서 가져와야 하는 데이터의 양이 많을수록 인덱스를 사용하는 것이 오히려 비효율적일 수 있습니다. (테이블 전체를 스캔하는 것보다 인덱스를 거치는 비용이 더 클 수 있음)

  2. 항상 테스팅하라:

    • 서비스 특성 의존: 최적의 인덱스 전략은 서비스의 특징(객체 깊이, 테이블 크기 등)에 따라 달라집니다.

    • 성능 측정: 따라서 인덱스 생성 후에는 반드시 explain() 함수(또는 유사 기능)를 사용하여 쿼리 실행 계획을 분석하고, 실제 쿼리 실행 시간을 측정하여 최적의 성능을 내도록 조정해야 합니다.

  3. 복합 인덱스 생성 순서: 같음, 정렬, 다중 값, 카디널리티:

    • 여러 필드를 결합하여 복합 인덱스를 생성할 때는 필드의 순서가 중요하며, 이 순서에 따라 인덱스 성능이 크게 달라질 수 있습니다.

    • 같음 (Equality) 조건 필드: = 연산자나 equal 함수 등 정확히 일치하는 값을 찾는 조건에 사용되는 필드를 가장 먼저 인덱스 순서에 포함시킵니다.

    • 정렬 (Sort) 조건 필드: 정렬(ORDER BY 등)에 사용되는 필드를 그 다음 순서로 설정합니다.

    • 다중 값 (Range) 조건 필드: >, < 등 범위 연산자를 사용하여 여러 값을 반환하는 조건에 사용되는 필드는 그 이후 순서로 설정합니다.

    • 카디널리티 (Cardinality) 높은 순서: 카디널리티는 특정 컬럼의 값이 얼마나 유니크한지를 나타내는 지표입니다. 카디널리티가 높은(즉, 고유한 값이 많은) 필드를 인덱스 후순위에 두는 것이 일반적이지만, MongoDB의 ESR(Equality-Sort-Range) 규칙에서는 범위 조건 이후 카디널리티에 대한 직접적인 순서 언급은 없으나, 전반적인 인덱스 선택도에 영향을 미칩니다. (여기서는 출처 의 '카디널리티가 높은 순서'를 따름)

조인 (Join)

조인이란 두 개 이상의 테이블을 특정 조건에 따라 연결하여 하나의 결과 집합으로 만드는 연산입니다. MySQL에서는 JOIN 쿼리로, MongoDB에서는 lookup이라는 집계 연산자로 조인과 유사한 작업을 수행할 수 있습니다.

MongoDB의 lookup 사용 시 주의

MongoDB에서 lookup 연산은 관계형 데이터베이스의 JOIN에 비해 성능이 떨어지는 것으로 여러 벤치마크 테스트에서 알려져 있습니다. 따라서 조인 작업이 많은 경우에는 관계형 데이터베이스 사용을 고려하는 것이 좋습니다.

조인의 종류

  • 내부 조인 (Inner Join): 두 테이블(A와 B)에서 조인 조건이 일치하는 행들만 결합하여 반환합니다. 즉, 두 테이블의 교집합에 해당합니다.

  • 왼쪽 조인 (Left Outer Join): 왼쪽 테이블(A)의 모든 행을 포함하고, 오른쪽 테이블(B)에서는 조인 조건에 일치하는 행만 가져옵니다. 오른쪽 테이블에 일치하는 행이 없으면 해당 필드는 NULL 값으로 채워집니다.

  • 오른쪽 조인 (Right Outer Join): 오른쪽 테이블(B)의 모든 행을 포함하고, 왼쪽 테이블(A)에서는 조인 조건에 일치하는 행만 가져옵니다. 왼쪽 테이블에 일치하는 행이 없으면 해당 필드는 NULL 값으로 채워집니다.

  • 합집합 조인 (Full Outer Join): 양쪽 테이블(A와 B)의 모든 행을 포함하며, 조인 조건에 일치하는 부분을 연결합니다. 일치하는 항목이 없는 경우, 누락된 쪽의 필드는 NULL 값으로 채워집니다.

조인의 원리

조인 연산은 특정 원리(알고리즘)를 기반으로 수행됩니다. 주요 조인 원리에는 중첩 루프 조인, 정렬 병합 조인, 해시 조인이 있습니다.

종류

특징

중첩 루프 조인 (Nested Loop Join)

  • 원리: 중첩된 for문과 유사하게 동작합니다. 첫 번째 테이블(Outer Table)의 각 행에 대해 두 번째 테이블(Inner Table)의 모든 행을 순차적으로 비교하여 조건에 맞는 행을 결합합니다.

  • 특징: 랜덤 접근에 대한 비용이 커서 대용량 테이블 간의 조인에는 비효율적일 수 있습니다.

  • 블록 중첩 루프 조인 (Block Nested Loop Join, BNLJ): NLJ를 개선한 방식으로, 외부 테이블의 행들을 일정 크기의 블록으로 나누어 각 블록 단위로 내부 테이블과 조인하여 I/O 비용을 줄입니다.

정렬 병합 조인 (Sort Merge Join)

  • 원리: 두 테이블을 조인할 필드를 기준으로 각각 정렬한 후, 정렬된 결과를 병합(Merge)하면서 조인 조건을 만족하는 행들을 결합합니다.

  • 특징: 조인 조건에 사용할 적절한 인덱스가 없거나, 대용량 테이블을 조인할 때, 또는 조인 조건이 범위 비교 연산자(<, >)를 포함할 때 주로 사용됩니다.

해시 조인 (Hash Join)

  • 원리: 해시 테이블을 기반으로 조인합니다. 두 테이블 중 작은 테이블(Build Table)을 읽어 메모리에 해시 테이블을 생성하고, 다른 테이블(Probe Table)을 스캔하면서 해시 테이블을 탐색하여 일치하는 행을 결합합니다.

  • 빌드 단계 (Build Phase): 두 입력 테이블 중 더 작은 테이블을 선택하여 조인 키를 해시 키로 사용하는 인메모리 해시 테이블을 구축합니다.

  • 프로브 단계 (Probe Phase): 다른 테이블을 읽으면서 각 행의 조인 키를 사용하여 빌드 단계에서 생성된 해시 테이블에서 일치하는 레코드를 찾아 결과로 반환합니다. 이 방식은 각 테이블을 한 번씩만 읽기 때문에 NLJ보다 효율적일 수 있습니다.

  • 특징: 동등 조인(=) 조건에서만 사용할 수 있습니다. 해시 테이블을 메모리에 생성하므로, 테이블 크기가 메모리에 적합할 때 중첩 루프 조인보다 효율적입니다. (메모리 부족 시 디스크 I/O 발생 가능) MySQL 8.0.18부터 지원되며, 사용 가능한 메모리 양은 join_buffer_size 시스템 변수로 제어됩니다.

핵심 포인트

인덱스

  • 필요성: 데이터를 빠르게 찾기 위한 장치, 책의 '찾아보기'와 유사.

  • B-트리: 인덱스의 일반적인 자료 구조 (루트-브랜치-리프 노드). 효율적인 탐색과 대수 확장성(깊이가 느리게 증가)이 장점.

  • 생성 방법:

    • MySQL: 클러스터형 인덱스(테이블당 1개, PK 또는 UNIQUE NOT NULL), 세컨더리 인덱스(CREATE INDEX).

    • MongoDB: _id 필드가 자동 기본키 인덱스, 복합 인덱스 설정 가능.

  • 최적화 기법:

    • 인덱스는 비용: 읽기 비용(이중 탐색), 수정 비용(인덱스 업데이트, B-트리 재조정) 발생. 무분별한 설정 및 대량 데이터 조회 시 비효율적.

    • 테스팅 필수: 서비스 특성에 따라 최적화 전략이 다르므로 explain() 등으로 반드시 테스트.

    • 복합 인덱스 순서: 같음 조건 → 정렬 조건 → 다중 값(범위) 조건 → 카디널리티 높은 순(출처 기반)으로 생성.

조인

  • 개념: 두 개 이상의 테이블을 묶어 하나의 결과물 생성. MySQL은 JOIN, MongoDB는 lookup (성능 주의).

  • 종류:

    • 내부 조인: 양쪽 테이블 모두 일치하는 행만 표기 (교집합).

    • 왼쪽 조인: 왼쪽 테이블 모든 행 표기, 오른쪽은 일치하는 행만 (없으면 NULL).

    • 오른쪽 조인: 오른쪽 테이블 모든 행 표기, 왼쪽은 일치하는 행만 (없으면 NULL).

    • 합집합 조인 (Full Outer Join): 양쪽 테이블 모든 행 표기 (일치 안 하면 NULL).

  • 원리:

    • 중첩 루프 조인: 중첩 for문 방식, 대용량에 부적합. (개선: 블록 중첩 루프 조인 )

    • 정렬 병합 조인: 각 테이블 조인 필드 기준 정렬 후 병합. 인덱스 없거나 범위 조건 시 유용.

    • 해시 조인: 작은 테이블로 메모리에 해시 테이블 생성 후 다른 테이블과 비교. 동등 조인에 효율적. (빌드 단계, 프로브 단계 )

출처

  • 면접을 위한 CS 전공지식 노트

- 컬렉션 아티클