자료구조

상위 노트: 컴퓨터 공학 기초 관련 노트: 메모리 관리, 알고리즘과 복잡도 분석

개요

자료구조는 데이터를 효율적으로 저장하고 접근하기 위한 체계다. 백엔드 엔지니어에게 자료구조는 단순한 이론이 아니라 데이터베이스 인덱스, 캐시 시스템, 분산 시스템의 동작 원리를 이해하는 열쇠다. Redis가 왜 빠른지, PostgreSQL이 어떻게 인덱스를 관리하는지, 분산 DB가 어떻게 데이터 일관성을 유지하는지 -- 모두 자료구조에서 시작한다.

1. 배열 (Array) vs 링크드 리스트 (Linked List)

연산별 시간 복잡도

캐시 효율성 -- 진짜 중요한 차이

배열 (Cache-friendly):
  메모리: [1][2][3][4][5][6][7][8]  ← 연속 배치
  캐시 라인 1개 로드 → 8개 원소 접근 가능
 
링크드 리스트 (Cache-unfriendly):
  메모리: [Node1]...[Node5]...[Node2]...[Node7]...
  각 노드가 메모리 곳곳에 흩어져 있음 → 캐시 미스 빈발

실무 의미: Big-O만 보면 링크드 리스트의 삽입/삭제가 O(1)이지만, 실제 성능에서는 캐시 미스 비용이 압도적이다. 메모리 관리에서 다룬 캐시 지역성(Cache Locality)이 실질적 성능을 결정한다.

백엔드 사용 사례

• 배열: JSON 배열, Redis List(내부적으로 ziplist/listpack 사용), 연속 로그 버퍼
• 링크드 리스트: LRU 캐시의 이중 연결 리스트, OS 프로세스 큐, 메모리 할당기의 free list

2. 해시 테이블 (Hash Table)

핵심 원리

키(Key)를 해시 함수에 통과시켜 배열의 인덱스로 변환, O(1) 시간에 데이터를 저장/조회한다.

Key: "user:1001"
  → hash("user:1001") = 7
  → table[7] = {name: "Kim", age: 30}
 
┌───┬───┬───┬───┬───┬───┬───┬────────────────┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7: user:1001  │ 8 │
└───┴───┴───┴───┴───┴───┴───┴────────────────┴───┘

충돌 해결 (Collision Resolution)

체이닝 (Chaining)

같은 인덱스에 링크드 리스트로 여러 항목을 저장:

table[3] → [key:A, val:1] → [key:B, val:2] → [key:C, val:3]

• 장점: 구현 간단, 적재율이 1을 넘어도 동작
• 단점: 포인터 추가 메모리, 캐시 효율 낮음

개방 주소법 (Open Addressing)

충돌 시 다른 빈 슬롯을 탐색:

Robin Hood Hashing

개방 주소법의 변형으로, 탐색 거리가 긴 원소가 짧은 원소를 밀어내는 방식:

• Rust 표준 라이브러리의 HashMap에서 사용
• 탐색 거리의 분산을 줄여 최악 케이스 성능 개선

해시 테이블이 사용되는 곳

3. 트리 (Tree) 자료구조

BST (Binary Search Tree)

왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 따르는 이진 트리:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

자가 균형 트리 (Self-Balancing Trees)

AVL Tree

• 모든 노드에서 왼쪽/오른쪽 서브트리 높이 차이가 최대 1
• 엄격한 균형 → 검색이 빠름, 삽입/삭제 시 회전 비용
• 사용: 메모리 내 인덱스, 사전 자료

Red-Black Tree

• 각 노드가 빨강 또는 검정
• 규칙: 루트는 검정, 빨강 노드의 자식은 검정, 모든 경로의 검정 노드 수 동일
• AVL보다 느슨한 균형 → 삽입/삭제 회전 횟수 적음
• 사용: Linux CFS 스케줄러 (프로세스 관리와 CPU 스케줄링), Java TreeMap, C++ std::map

B-Tree와 B+Tree -- 데이터베이스의 심장

B-Tree

• 다분 탐색 트리: 하나의 노드에 여러 키를 저장
• 디스크 I/O 최적화: 노드 크기를 디스크 블록(4KB~16KB)에 맞춤
• 차수(Order) m인 B-Tree: 각 노드는 최대 m-1개의 키, m개의 자식

B-Tree (차수 4):
              [10 | 20 | 30]
             /    |    |    \
    [3|5|7] [12|15] [22|25] [35|40|45]

B+Tree -- DB 인덱스의 표준

B-Tree의 변형으로, 데이터베이스 인덱스의 사실상 표준:

B+Tree:
내부 노드: 키만 저장 (라우팅 역할)
         [10 | 20 | 30]
        /    |    |    \
리프 노드: 키+데이터, 연결 리스트로 연결
[3|5|7] ←→ [10|12|15] ←→ [20|22|25] ←→ [30|35|40]

왜 B+Tree가 DB에 최적인가?

1. 높은 팬아웃 → 트리 높이가 낮음 → 디스크 I/O 최소화
2. 리프 연결 리스트 → 범위 쿼리 (WHERE age BETWEEN 20 AND 30) 효율적
3. 내부 노드가 작음 → 캐시에 더 많이 적재 가능

PostgreSQL, MySQL InnoDB, SQLite 모두 B+Tree 기반 인덱스를 사용한다.

4. 힙 (Heap)

정의

완전 이진 트리 + 힙 속성 (부모 >= 자식: Max Heap, 부모 <= 자식: Min Heap)

Min Heap:
        1
       / \
      3   5
     / \ / \
    7  9 8  10

연산 복잡도

백엔드 활용

5. 그래프 (Graph)

표현 방식

인접 행렬 (Adjacency Matrix)

    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  0  1 ]
C [ 1  0  0  1 ]
D [ 0  1  1  0 ]

• 공간: O(V^2)
• 간선 확인: O(1) -- matrix[u][v]
• 적합: 밀집 그래프 (Dense Graph)

인접 리스트 (Adjacency List)

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

• 공간: O(V + E)
• 간선 확인: O(degree(v))
• 적합: 희소 그래프 (Sparse Graph) -- 대부분의 실세계 그래프

백엔드에서의 그래프

6. LSM-Tree (Log-Structured Merge Tree)

핵심 개념

쓰기 최적화 자료구조. B+Tree가 읽기 최적화인 반면, LSM-Tree는 높은 쓰기 처리량을 위해 설계되었다.

동작 원리

쓰기 요청 → WAL (Write-Ahead Log, 디스크)
        → MemTable (메모리, 정렬된 구조)
               │ (가득 차면)
               ▼
          Immutable MemTable
               │ (플러시)
               ▼
          SSTable L0 (디스크)
               │ (컴팩션)
               ▼
          SSTable L1
               │ (컴팩션)
               ▼
          SSTable L2
               │
              ...

구성 요소

읽기 과정

읽기 요청 → MemTable 확인 → L0 SSTable 확인 → L1 → L2 → ...
         (빠름)         (Bloom Filter로 빠른 부정 판단)

B+Tree vs LSM-Tree

사용하는 시스템

2026년 최신 최적화

• SpanDB: NVMe SSD의 속도를 활용하여 WAL과 상위 LSM 레벨을 빠른 SSD에 배치
• 동적 스케줄링: NVMe 프로토콜 특성을 활용하여 플러시/컴팩션을 클라이언트 요청과 간섭 없이 수행
• Tiered Compaction: 레벨별 컴팩션 대신 계층별로 SSTable을 묶어 쓰기 증폭 감소

7. Bloom Filter -- 확률적 자료구조

개념

원소가 집합에 속하는지 확률적으로 판단하는 자료구조:

• "없음"이라고 답하면 → 확실히 없음 (False Negative 없음)
• "있음"이라고 답하면 → 있을 수도 있고 없을 수도 있음 (False Positive 가능)

구조

비트 배열: [0][0][0][0][0][0][0][0][0][0]
             ↑        ↑     ↑
hash1("key") hash2("key") hash3("key")
 
삽입 후:  [0][1][0][0][1][0][1][0][0][0]
 
검색: 3개의 해시 위치가 모두 1이면 "아마 있음"
      하나라도 0이면 "확실히 없음"

False Positive 확률

비트 배열 크기 m, 해시 함수 개수 k, 삽입된 원소 수 n일 때:

P(false positive) ≈ (1 - e^(-kn/m))^k

백엔드 활용

8. Skip List

개념

정렬된 링크드 리스트에 **여러 레벨의 "고속도로"**를 추가하여 O(log n) 검색을 달성:

Level 3: HEAD ────────────────────────────→ 50 ─────→ NIL
Level 2: HEAD ──────→ 20 ────────────────→ 50 ─────→ NIL
Level 1: HEAD ──→ 10 → 20 ──→ 30 ──────→ 50 → 60 → NIL
Level 0: HEAD → 5 → 10 → 20 → 25 → 30 → 50 → 55 → 60 → NIL

시간 복잡도

B+Tree 대비 장점

• 구현이 단순 (회전 연산 불필요)
• Lock-free 구현이 가능 → 동시성에 유리
• **Redis Sorted Set(ZSET)**이 Skip List를 사용하는 이유

9. CRDT (Conflict-free Replicated Data Types)

문제: 분산 시스템의 충돌

여러 노드가 동시에 같은 데이터를 수정하면 충돌이 발생한다. CRDT는 수학적으로 충돌이 불가능한 자료구조다.

핵심 원리

모든 편집 연산을 **교환 법칙(Commutative)**이 성립하는 연산으로 변환:

노드 A: counter += 1 (A: 1)
노드 B: counter += 3 (B: 3)
 
병합: A + B = 1 + 3 = 4 (순서 무관!)

CRDT 유형

실세계 사용

CAP 정리와의 관계

CAP 정리: Consistency, Availability, Partition Tolerance 중 2개만 선택 가능
 
CRDT는 AP (Availability + Partition Tolerance) 시스템에서
"결국 일관성"(Eventual Consistency)을 수학적으로 보장한다.
→ 알고리즘과 복잡도 분석의 Raft/Paxos는 CP 시스템의 해결책

10. 확률적 자료구조 (Probabilistic Data Structures)

HyperLogLog -- 유일 원소 수 추정

대규모 데이터셋에서 **고유 원소 수(Cardinality)**를 극소 메모리로 추정:

# Redis HyperLogLog
PFADD visitors "user1" "user2" "user3"
PFCOUNT visitors
# (integer) 3
# 10억 개를 넣어도 ~12KB만 사용!

Count-Min Sketch -- 빈도 추정

스트리밍 데이터에서 특정 항목의 출현 빈도를 근사적으로 추정:

• 실제 빈도 이상의 값을 반환 (과대 추정은 가능, 과소 추정은 없음)
• 사용: 네트워크 트래픽 분석, 핫 아이템 탐지, 이상 탐지

Cuckoo Filter

Bloom Filter의 개선:

• 삭제 연산 지원 (Bloom Filter는 삭제 불가)
• 더 나은 공간 효율 (적재율이 높을 때)
• 사용: 중복 탐지, 네트워크 패킷 필터링

정리: 백엔드 시스템별 핵심 자료구조

다음 노트

→ 알고리즘과 복잡도 분석: 정렬, 탐색, 동적 프로그래밍, 분산 시스템 알고리즘