---
id: e80ed40ea024585819cc03207d51db23
author: snowmerak
title: 활기찬 비트맵
description: 데이터베이스 비트맵 인덱스 개념부터 Roaring Bitmap의 동작 원리, Go 언어 활용법까지. 대규모 데이터셋 효율적 처리를 위한 비트맵 최적화를 탐구합니다.
language: ko
date: 2025-09-08T13:30:39.840979719Z
path: /blog/posts/vibrant-bitmap-z1743872f
category: database
---

## 비트맵이란?

> 여기서 비트맵은 인덱스의 한 종류입니다. 그래픽스 생각하고 들어오셨다면 뒤로가기 누르시면 됩니다.

### 기본 개념

비트맵은 데이터베이스의 인덱싱 기술의 한 형태입니다. 특정 칼럼의 값을 비트 배열이나 벡터의 한 원소나 형태로 표현하여, 각 비트가 해당 칼럼의 특정 값이 존재하는지 여부를 나타냅니다. 그래서 가장 기본적인 형태는 각 row에 대해 비트 인덱스를 할당하고 존재 여부를 0과 1로 표현하는 것입니다.

예를 들어, 성별 칼럼이 있는 테이블이 있다고 가정해봅시다. 이 테이블에 5개의 row가 있고, 성별 칼럼의 값이 다음과 같다고 합시다:

1. 남성
2. 여성
3. 남성
4. 여성
5. 기타

이 경우, 성별 칼럼에 대한 비트맵 인덱스는 다음과 같이 표현될 수 있습니다:

- 남성: 10100
- 여성: 01010
- 기타: 00001

### 그래서 진짜 어디다가 쓰냐면

그래서 단순히 저걸 나타내기 위한 것이 아니라고 다들 생각할 것입니다. 비트맵 인덱스를 제대로 사용해보기 위해 다음 경우를 고려해봅시다.

```SQL
CREATE TABLE IF NOT EXISTS Users (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    active BOOLEAN,
    sex BOOLEAN,
    age INT
);
```

이 테이블에 1,000,000개의 row가 있다고 가정해봅시다. 그리고 다음과 같은 쿼리를 실행한다고 합시다.

```SQL
SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;
```

이 쿼리는 active와 sex 칼럼이 모두 TRUE인 row를 찾습니다. 그러면 가장 빠르게 두 칼럼이 TRUE인 조건을 성립하는 row를 찾는 방법으로 bit and 연산을 활용할 수 있을 것입니다.

- active 칼럼에 대한 비트맵 인덱스가 `1100110011...` (1,000,000개 비트 배열)이 미리 인덱싱 되어 있고,
- sex 칼럼에 대한 비트맵 인덱스가 `1010101010...` (1,000,000개 비트 배열)이 미리 인덱싱 되어 있다고 합시다.

그러면 두 비트맵 인덱스에 대해 bit and 연산을 수행하여, 두 칼럼이 모두 TRUE인 row를 빠르게 찾을 수 있습니다. 단순 비트 연산이기 때문에 다른 인덱스 스캔보다 훨씬 빠르게 결과를 얻을 수 있을 것입니다.

### 트레이드 오프

비트맵 인덱스는 매우 효율적일 수 있지만, 몇 가지 트레이드 오프가 있습니다. 다른 단점이 많지만 지금은 하나만 짚고 넘어가겠습니다.

바로 비트맵 인덱스는 낮은 카디널리티(즉, 칼럼에 가능한 값의 수가 적은 경우)에 더 적합합니다. 높은 카디널리티의 칼럼에 비트맵 인덱스를 사용하면 비트맵이 매우 커질 수 있습니다.

높은 카디널리티의 칼럼에 비트맵 인덱스를 사용하면, 각 고유 값에 대해 별도의 비트맵을 생성해야 하므로, 저장 공간이 많이 필요할 수 있습니다. 예를 들어, 만약 칼럼에 1,000,000개의 고유 값이 있다면, 1,000,000개의 비트맵을 생성해야 하므로, 이는 매우 비효율적일 수 있습니다.

## 그래서 우리는

높은 카디널리티에서 오는 비트맵을 대체하여 Roaring Bitmap이라는 것을 사용할 수 있습니다. Roaring Bitmap은 여러가지 특성이 있지만, 가장 큰 기반 철학과 특성은 `데이터의 밀도에 따라 가장 적합한 저장 방식을 동적으로 선택하여 압축률과 연산 속도 모두 극대화하는 것`입니다.

### Roaring Bitmap의 기본 개념

#### 2단계 인덱싱

Roaring Bitmap은 정수 하나를 저장하기 위해 먼저 다음 2단계를 거칩니다. 말이 2단계 인덱싱이지, 그냥 2차원 배열이라고 생각하시면 됩니다.

- 상위 16비트 추출: 정수의 상위 16비트를 추출하여, 이를 인덱스로 사용합니다. 총 65536만큼의 길이를 가진 2차원 배열 중 바깥 배열의 인덱스가 되는 것입니다. 이 배열은 후술할 컨테이너의 주소를 저장합니다.
- 하위 16비트 추출: 정수의 하위 16비트를 추출하여, 이를 컨테이너 내에서의 위치로 사용합니다.

#### 컨테이너

이 컨테이너는 방금 비유했던 대로 2차원 배열 중 안쪽 배열에 해당합니다. 하지만 상위 16비트의 그것과는 다르게, 이 컨테이너는 내부 데이터가 얼마나 있냐에 따라 내부 구조가 달라집니다. Roaring Bitmap은 다음 3가지 컨테이너를 지원합니다.

- Array Container: 이 컨테이너는 내부에 저장된 데이터가 적을 때 사용됩니다. 구체적으로, 4096개 이하의 원소를 저장할 때 사용됩니다. 이 컨테이너는 단순히 정렬된 정수 배열로 구현되어 있습니다. 이진 탐색 하여 원소를 찾을 수 있습니다.
- Bitmap Container: 이 컨테이너는 내부에 저장된 데이터가 많을 때 사용됩니다. 구체적으로, 4096개 초과의 원소를 저장할 때 사용됩니다. 이 컨테이너는 65536비트(8192바이트)의 비트맵으로 구현되어 있습니다. 각 비트는 해당 위치의 정수가 존재하는지 여부를 나타냅니다.
- Run Container: 이 컨테이너는 연속된 정수 범위를 저장할 때 사용됩니다. 예를 들어, 1, 2, 3, 4, 5와 같은 연속된 정수들을 저장할 때 효율적입니다. 이 컨테이너는 (시작 값, 길이) 쌍의 리스트로 구현되어 있습니다. 만약 다 있으면? 그냥 처음부터 끝까지 다 있다는 뜻이니, (0, 65536) 하나만 저장하면 됩니다.

이러한 방식은 Roaring Bitmap이 매우 효율적으로 메모리를 사용하고, 다양한 데이터 밀도에 대해 최적의 성능을 제공할 수 있게 합니다.

### Roaring Bitmap의 기능

#### 기본 기능

Roaring Bitmap은 다음과 같은 기본 기능을 제공합니다.

- 삽입: 새로운 정수를 비트맵에 추가합니다. 이 과정에서 적절한 컨테이너를 선택하거나, 필요에 따라 컨테이너를 변환할 수 있습니다.
- 삭제: 기존 정수를 비트맵에서 제거합니다. 이 과정에서도 컨테이너의 상태에 따라 적절한 처리가 이루어집니다.
- 검색: 특정 정수가 비트맵에 존재하는지 여부를 확인합니다. 이 과정은 매우 빠르게 수행됩니다.

#### 집합 연산

Roaring Bitmap은 또한 다음과 같은 집합 연산을 지원합니다.

- 합집합 (Union): 두 비트맵의 모든 원소를 포함하는 새로운 비트맵을 생성합니다.
- 교집합 (Intersection): 두 비트맵에 모두 존재하는 원소만을 포함하는 새로운 비트맵을 생성합니다.
- 대칭 차집합 (Symmetric Difference): 두 비트맵 중 하나에만 존재하는 원소를 포함하는 새로운 비트맵을 생성합니다.

이러한 연산들은 비트맵의 컨테이너 유형에 따라 최적화되어 매우 빠르게 수행됩니다.

### Go 언어에서

Go 언어에서는 `github.com/RoaringBitmap/roaring` 패키지를 사용하여 Roaring Bitmap을 쉽게 활용할 수 있습니다. 이 패키지는 Roaring Bitmap의 모든 기능을 제공하며, Go 언어의 특성에 맞게 최적화되어 있습니다.

#### 설치

```bash
go get github.com/RoaringBitmap/roaring/v2
```

#### 사용 예시

```go
package main

import (
	"log"

	"github.com/RoaringBitmap/roaring/v2"
)

func main() {
	b1 := roaring.BitmapOf(1, 2, 3, 4)     // 1, 2, 3, 4로 초기화
	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12로 초기화

	b1.Add(5)  // 5 추가
	b2.Add(10) // 10 추가

	b2.Remove(12) // 12 제거

	and := roaring.FastAnd(b1, b2)
	or := roaring.FastOr(b1, b2)

	// bitmap 연산이 원본을 변경하므로 복제본을 만들어 사용
	xor := b1.Clone()
	xor.Xor(b2)

	log.Printf("and result: %v", and.ToArray())
	log.Printf("or result: %v", or.ToArray())
	log.Printf("xor result: %v", xor.ToArray())
}
```

```shell
2025/09/08 22:16:27 and result: [2 4]
2025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
2025/09/08 22:16:27 xor result: [1 3 5 6 8 10]
```

위 예시 코드에서 나오지 않은 주요 기능들로

- `Contains(x uint32) bool`: 특정 값이 비트맵에 존재하는지 확인
- `GetCardinality() uint64`: 비트맵에 포함된 원소의 개수 반환
- `Rank(x uint32) uint64`: 특정 값 이하의 원소 개수 반환
- `ToBytes() ([]byte, error)`: 비트맵을 바이트 슬라이스로 직렬화
- `FromBytes(data []byte) error`: 바이트 슬라이스에서 비트 맵 복원
- `Clone() *Bitmap`: 비트맵의 복제본 생성
- `Clear()`: 비트맵 초기화
- `NextValue(x uint32) int64`: x보다 크거나 같은 다음 원소 반환
- `PreviousValue(x uint32) int64`: x보다 작거나
- `Maximum() uint32`: 비트맵에서 가장 큰 원소 반환
- `Minimum() uint32`: 비트맵에서 가장 작은 원소 반환

이런 기능들이 있습니다. 자세한 내용은 [공식 문서](https://pkg.go.dev/github.com/RoaringBitmap/roaring/v2)를 참고하세요.

참고로 roaring 패키지는 내부에 uint32 뿐만 아니라 uint64를 지원하는 패키지를 포함하고 있습니다. 거의 동일한 인터페이스를 제공함으로 바로 교체하여 사용할 수 있습니다.

```go
package main

import (
	"log"

	"github.com/RoaringBitmap/roaring/v2/roaring64"
)

func main() {
	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // 1, 2, 3, 4로 초기화
	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12로 초기화

	b1.Add(5)  // 5 추가
	b2.Add(10) // 10 추가

	b2.Remove(12) // 12 제거

	and := roaring64.FastAnd(b1, b2)
	or := roaring64.FastOr(b1, b2)

	// bitmap 연산이 원본을 변경하므로 복제본을 만들어 사용
	xor := b1.Clone()
	xor.Xor(b2)

	log.Printf("and result: %v", and.ToArray())
	log.Printf("or result: %v", or.ToArray())
	log.Printf("xor result: %v", xor.ToArray())
}
```

### 마치며

Roaring Bitmap은 높은 카디널리티의 정수 집합을 효율적으로 저장하고 조작할 수 있는 강력한 도구입니다. Go 언어에서 `github.com/RoaringBitmap/roaring` 패키지를 사용하면, Roaring Bitmap의 모든 기능을 쉽게 활용할 수 있습니다. 이 패키지는 다양한 컨테이너 유형과 최적화된 연산을 통해, 메모리 사용량과 성능을 극대화합니다. 데이터베이스 인덱싱, 로그 분석, 통계 계산 등 다양한 분야에서 Roaring Bitmap을 활용하여 효율적인 데이터 처리를 구현할 수 있습니다.

Roaring Bitmap은 특히 대규모 데이터셋에서 높은 성능을 발휘하며, 다양한 응용 프로그램에서 유용하게 사용될 수 있습니다. Go 언어의 간결하고 효율적인 문법과 결합하여, Roaring Bitmap은 개발자들에게 강력한 도구를 제공합니다. 앞으로도 Roaring Bitmap의 발전과 함께, 더 많은 기능과 최적화가 이루어질 것으로 기대됩니다.

> 전 이걸 왜 했냐구요? 시계열 데이터베이스에서 각 태그 별 인덱싱과 빠른 합집합 연산을 위해서요.