해시 인덱스

해시 인덱스는 「이 열의 값이 이것과 같은 행」을 곧바로 찾아 줍니다. 찾을 값을 짧은 수 하나로 바꿉니다. 그 수가 가리키는 칸만 열어 봅니다. 값을 크기 순서로 늘어놓지는 않아서 크고 작음을 따지는 질문에는 답하지 못합니다.

쉽고 빠른 이해

해시 인덱스는 값이 같은 행을 찾는 일 하나만 줄여 주는 찾아보기입니다. 회원 표에서 이메일이 [email protected] 인 행을 꺼내는 것이 그런 일입니다.

이게 없으면 데이터베이스는 회원 표의 모든 행을 읽어 이메일을 하나씩 견줍니다. 회원이 백만 명이면 백만 행을 읽습니다.

어떻게 도나:

찾을 값을 해시 함수에 넣어 수 하나를 얻습니다
그 수로 칸 번호를 계산해 칸 하나만 읽습니다
칸에 적힌 행 위치를 따라가 표의 그 행을 꺼냅니다

대가도 있습니다. 순서가 없어서 범위로 묻는 질문과 정렬에는 못 씁니다. 행을 넣고 지울 때마다 인덱스도 같이 고쳐야 해서 쓰기에 드는 비용이 늘어납니다.

상세

해시 인덱스가 값 하나에서 표의 행까지 어떤 길로 잇는지를 봅니다. 예는 회원 표 하나와 칸 네 개짜리 작은 인덱스로 듭니다.

인덱스가 하는 일

인덱스는 표 옆에 따로 두는 찾아보기입니다. 어떤 열의 값을 주면 그 값을 가진 행이 표의 어디에 있는지 알려 줍니다. 인덱스가 없으면 데이터베이스는 표의 모든 행을 읽어 조건에 맞는지 하나씩 봅니다. 표를 전부 읽는 것이 테이블 풀 스캔입니다.

디스크 페이지는 디스크에서 한 번에 읽고 쓰는 덩어리입니다. 표도 인덱스도 이 덩어리 단위로 오갑니다.

인덱스가 알려 주는 「표의 어디」는 행 하나를 가리키는 짧은 값입니다. 이 값이 행 식별자입니다. 어느 디스크 페이지의 몇 번째 행인지를 담는 식입니다.

인덱스에 담긴 값 하나가 표의 어느 행을 가리키는지 그려 보면 이렇습니다. 이메일은 앞부분만 적었습니다.

flowchart TD
    subgraph IDX["인덱스"]
        I1["kim · 행 식별자"]
        I2["park · 행 식별자"]
    end
    subgraph P7["회원 표 · 7번 디스크 페이지"]
        R1["1번 행 · kim"]
        R2["2번 행 · lee"]
    end
    subgraph P9["회원 표 · 9번 디스크 페이지"]
        R3["1번 행 · park"]
        R4["2번 행 · choi"]
    end
    I1 --> R1
    I2 --> R3

인덱스 쪽의 「kim · 행 식별자」는 회원 표 7번 디스크 페이지의 1번 행을 가리킵니다. 인덱스에서 행 식별자를 얻으면 표에서는 그 페이지의 그 행 하나만 읽습니다.

인덱스를 만드는 방법은 여럿입니다. 값을 정렬해 담는 B-tree 가 널리 쓰이는 쪽입니다. 값을 해시해 담는 것이 해시 인덱스입니다. 둘은 답할 수 있는 질문이 다릅니다.

값에서 칸까지

해시 인덱스는 칸 여러 개를 늘어놓습니다. 이 칸 하나를 버킷이라고 부릅니다. 각 버킷에는 인덱스를 건 열의 값과 행 식별자를 한 쌍으로 담습니다. 값과 행 식별자를 묶은 이 한 쌍이 항목입니다.

어느 버킷에 담을지는 해시 함수가 정합니다. 해시 함수는 어떤 데이터든 받아 정수 하나로 줄입니다. 그 정수를 해시값이라고 부릅니다. 같은 값을 넣으면 언제나 같은 해시값이 나옵니다.

해시값은 버킷 수보다 훨씬 클 수 있습니다. 그래서 해시값을 버킷 수로 나눈 나머지를 버킷 번호로 씁니다. 나머지는 늘 0부터 버킷 수보다 하나 작은 수 사이에 들어옵니다.

두 이메일의 해시값이 3105 와 3107 이라고 해 봅니다. 버킷이 네 개면 버킷 번호는 이렇게 나옵니다.

3105 % 4   // 1
3107 % 4   // 3

두 해시값의 차이는 둘뿐입니다. 그래도 버킷은 1번과 3번으로 갈렸습니다. 나머지는 원래 값의 크기를 물려받지 않습니다.

찾는 길

찾기는 값 하나를 받아 행까지 가는 짧은 길입니다.

flowchart TD
    V["찾을 값"] --> H["해시 함수로 해시값을 얻는다"]
    H --> M["버킷 수로 나눈 나머지를 구한다"]
    M --> B["그 번호의 버킷을 읽는다"]
    B --> C{"같은 값이 적힌 항목이 있나"}
    C -->|있다| R["행 식별자를 따라가 행을 읽는다"]
    C -->|없다| N["맞는 행이 없다"]

버킷을 읽은 뒤에 값을 한 번 더 견주는 대목을 눈여겨봐야 합니다. 다른 값이 같은 버킷에 와 있을 수 있어서입니다. 그 경우가 다음 소절입니다.

같은 버킷으로 몰린 값

서로 다른 두 값이 같은 버킷 번호를 받는 일을 해시 충돌이라고 부릅니다. 충돌은 피할 수 없습니다. 열에 들어올 수 있는 값은 끝없이 많습니다. 버킷 수는 정해져 있습니다.

그래서 버킷에는 항목 하나만 담지 않습니다. 같은 버킷으로 온 항목을 나란히 담아 둡니다. 찾을 때 그 안에서 값을 견줍니다. 버킷 하나는 디스크 페이지 한 장이라 담을 수 있는 항목 수가 정해져 있습니다.

한 버킷에 항목이 넘치면 페이지를 하나 더 달아 이어 붙입니다. 이렇게 덧붙인 페이지가 넘침 페이지입니다.

아래 그림은 버킷 네 개 가운데 둘만 그린 것입니다. 항목에는 이메일의 앞부분만 적었습니다. 점선은 버킷이 넘쳐 페이지를 하나 더 단 것이고, 굵은 선은 choi 를 찾을 때 읽는 길입니다.

flowchart TD
    subgraph 버킷배열["버킷 배열 · 네 칸 중 둘"]
        B1["1번 버킷"]
        B3["3번 버킷"]
    end
    B1 --> E1["kim · 행 식별자"]
    B1 --> E2["park · 행 식별자"]
    B1 -. 넘치면 .-> OV["넘침 페이지"]
    OV --> E3["choi · 행 식별자"]
    B3 --> E4["lee · 행 식별자"]
    linkStyle 2,3 stroke-width:3px

1번 버킷에는 항목 셋이 몰려서 넘침 페이지가 하나 붙었습니다. choi 를 찾으려면 1번 버킷을 읽고 넘침 페이지까지 읽어야 합니다. 그림의 굵은 선이 그 길입니다. 넘침 페이지가 길게 이어질수록 버킷 하나를 읽는 데 디스크 읽기가 여러 번 듭니다.

행을 넣고 지울 때

행을 새로 넣으면 그 행의 열 값으로 버킷을 정해 항목을 하나 답니다. 행을 지우면 인덱스에서도 그 항목을 뺍니다. 인덱스를 건 열의 값을 고치면 버킷 번호가 달라질 수 있습니다. 그때는 옛 버킷에서 뺀 뒤 새 버킷에 답니다.

그래서 인덱스는 읽기를 줄이는 대신 쓰기를 늘립니다. 인덱스를 여럿 걸어 둔 표는 행 하나를 넣을 때 인덱스 수만큼 더 씁니다. 이렇게 한 번의 쓰기가 여러 번의 쓰기로 불어나는 것을 쓰기 증폭이라고 부릅니다.

인덱스는 표와 아귀가 맞아야 쓸모가 있습니다. 갑자기 꺼진 뒤에도 맞아 있어야 하므로, 인덱스를 고친 기록도 WAL(Write-Ahead Log, 미리 쓰는 로그)에 남깁니다.

인덱스를 둘 걸어 둔 표에 행 하나를 넣으면 쓰기가 이렇게 갈라집니다.

flowchart TD
    W["행 하나 넣기"] --> T["표 페이지 쓰기"]
    W --> A["인덱스 A 버킷 쓰기"]
    W --> B["인덱스 B 버킷 쓰기"]
    W --> L["WAL 기록"]

넣으라고 한 행은 하나인데 디스크에는 네 번 씁니다.

버킷 늘리기

표의 행이 늘면 버킷마다 담긴 항목도 늘어납니다. 담긴 항목 수를 버킷 수로 나눈 값이 적재율입니다. 적재율이 정해 둔 문턱을 넘으면 버킷 수를 늘립니다.

버킷 수가 바뀌면 번호를 구할 때 나누는 수도 바뀝니다. 그러면 항목이 있어야 할 버킷도 바뀌므로 옮겨 담아야 합니다. 이 옮겨 담기를 리해싱이라고 부릅니다.

해시값이 5 · 9 · 6 · 12 인 항목 넷을 네 칸에 담았다고 해 봅니다. 나누는 수가 4라서 항목은 이렇게 앉습니다.

flowchart TD
    subgraph BEFORE["늘리기 전 · 버킷 네 칸"]
        B0["0번 버킷"] --> I12["해시값 12"]
        B1["1번 버킷"] --> I5["해시값 5"]
        B1 --> I9["해시값 9"]
        B2["2번 버킷"] --> I6["해시값 6"]
        B3["3번 버킷"]
    end

칸을 여덟 개로 늘리면 나누는 수도 8이 됩니다. 같은 항목 넷이 이렇게 다시 앉습니다.

flowchart TD
    subgraph AFTER["늘린 뒤 · 버킷 여덟 칸"]
        C0["0번 버킷"]
        C1["1번 버킷"] --> J9["해시값 9"]
        C2["2번 버킷"]
        C3["3번 버킷"]
        C4["4번 버킷"] --> J12["해시값 12"]
        C5["5번 버킷"] --> J5["해시값 5"]
        C6["6번 버킷"] --> J6["해시값 6"]
        C7["7번 버킷"]
    end

네 칸에서 1번에 함께 앉았던 5와 9가 여덟 칸에서는 5번과 1번으로 갈립니다. 12도 0번에서 4번으로 옮겨 앉습니다. 제자리인 것은 9 하나뿐입니다.

해시테이블은 같은 방식을 메모리 안에서 쓰는 자료구조입니다. 메모리 안의 해시테이블이라면 옮기는 비용이 크지 않습니다. 디스크에 있는 인덱스는 다릅니다. 인덱스가 크면 다시 만드는 동안 인덱스 크기만큼 디스크를 읽고 씁니다. 그 사이 인덱스를 쓰는 조회는 기다립니다.

그래서 디스크 인덱스는 한 번에 다 옮기지 않습니다. 버킷을 조금씩 쪼개는 방법을 씁니다. 그런 방법으로 선형 해싱과 확장 해싱이 있습니다. 어떻게 쪼개는지는 각 항목에서 다룹니다.

못 하는 질문

해시값은 원래 값의 크고 작음을 물려받지 않습니다. 가까운 두 값이 먼 버킷으로 갈 수 있습니다. 먼 두 값이 같은 버킷에 앉을 수도 있습니다. 그래서 답할 수 없는 질문이 생깁니다.

이런 질문	답하나	왜
값이 이것과 같은 행	답한다	버킷 하나만 읽으면 된다
값이 이것보다 큰 행	못 한다	버킷 번호에 순서가 없다
값이 이 둘 사이인 행	못 한다	어느 버킷을 읽을지 고를 수 없다
값이 이 글자로 시작하는 행	못 한다	값의 일부만으로는 해시값이 안 나온다
결과를 그 열 순서로 정렬	못 한다	인덱스를 훑어도 값 순서가 안 나온다
여러 열에 건 인덱스에서 앞 열만 주고 찾기	못 한다	열을 모아 해시하므로 전부 있어야 한다

B-tree 는 값을 정렬해 담아서 이 질문들에 전부 답합니다. 대신 값 하나를 찾을 때 뿌리에서 잎까지 여러 단계를 내려갑니다. 해시 인덱스는 그 단계 없이 버킷 하나로 갑니다.

두 인덱스의 모양을 나란히 놓으면 그 차이가 보입니다.

flowchart TD
    subgraph BT["B-tree · 뿌리에서 잎까지"]
        T0["뿌리 노드"] --> T1["가지 노드"]
        T0 --> T2["가지 노드"]
        T1 --> L1["잎 노드"]
        T1 --> L2["잎 노드"]
        T2 --> L3["잎 노드"]
        T2 --> L4["잎 노드"]
    end
    subgraph HI["해시 인덱스 · 버킷 한 칸"]
        H0["찾을 값"] --> H1["그 번호의 버킷"]
    end

B-tree 는 뿌리 노드에서 가지 노드를 거쳐 잎 노드까지 내려갑니다. 층이 깊어지면 읽는 노드도 그만큼 늘어납니다. 해시 인덱스는 값으로 번호를 구해 버킷 한 칸을 읽고 끝납니다.

복잡도

자료구조가 얼마나 빨리 답하는지는 빅오 표기법으로 적습니다. O(1) 은 데이터가 늘어도 걸리는 시간이 거의 늘지 않는다는 뜻입니다. 아래에서 n 은 인덱스에 담긴 항목 수입니다.

연산	평균	최악
값이 같은 항목 찾기	O(1)	O(n)
항목 넣기	O(1)	O(n)
항목 지우기	O(1)	O(n)
공간	O(n)	O(n)

평균이 O(1) 인 까닭은 버킷 하나에 담긴 항목 수를 문턱 아래로 묶어 두기 때문입니다. 버킷 하나를 읽는 디스크 읽기가 대개 한 번으로 끝납니다.

최악이 O(n) 인 까닭은 모든 항목이 한 버킷으로 몰릴 수 있어서입니다. 인덱스를 건 열에 같은 값이 잔뜩 들어 있으면 그렇게 됩니다. 열이 가진 값의 가짓수를 카디널리티라고 부릅니다. 이 수가 적은 열이 그런 열입니다.

쓸 때와 안 쓸 때

인덱스를 걸려는 열을 기준으로 가릅니다. 값이 겹치는지, 범위로 묻는지, 정렬해 내보내는지를 봅니다.

인덱스를 걸려는 열	해시 인덱스가 맞나
이메일이나 주문 번호처럼 값이 겹치지 않는 열	맞다. 값 하나로 행 하나를 집는다
같음만 따지는 조건에 거의 늘 쓰이는 열	맞다. 인덱스가 하는 일이 그것뿐이다
날짜나 금액처럼 범위로 묻는 열	안 맞다. B-tree 를 건다
결과를 그 열 순서로 정렬해 내보내는 열	안 맞다. 순서를 안 준다
값의 가짓수가 적은 열	안 맞다. 한 버킷에 몰린다
같음 조회와 범위 조회를 둘 다 하는 열	안 맞다. B-tree 하나로 둘 다 받는다

B-tree 는 같음 조회도 받습니다. 인덱스를 하나만 건다면 B-tree 로 두는 편이 무난한 까닭입니다. 해시 인덱스를 따로 거는 것은 같음 조회만 잦을 때입니다. 값이 길어 정렬해 담는 인덱스가 커질 때도 그렇습니다.