7조 물리적 데이터베이스 미션

B+ 트리 인덱싱

B-tree 의 등장 배경

만든 사람 : R. Bayer, E. McCreight
등장 배경 : 동적 랜덤 액세스 파일을 위한 인덱스의 조직과 유지 관리를 고려.
성능 개선 : 이러한 인덱스 조직 방식은 키의 검색, 삽입 및 삭제를 O(log_k I) 시간 복잡도로 가능하게 합니다.

B-tree 의 동작 방식

기본구조
- 각 노드는 여러 개의 키와 자식 포인터를 가집니다.
- 키는 오름차순으로 정렬되어 있음
- 노드의 자식 수는 키의 수보다 하나 더 많다.
- B-Tree의 모든 Leaf노드는 같은 레벨에 있다.
삽입 연산
삭제 연산
101차 B tree 기준 예시
호눅스님의 말씀
- 페이지 대략 16KB
- B+Tree가 5차까지 갔다는건?
  - Integer타입 4byte의 키로 이루어져 이있다면, 16KB / 4 = 4KB
  - 5차까지 가면 4KB^1000이니까 6차를 갈 일은 거의 없지 않을까? ㄷㄷ
- 정말 대단한 트리구나~ 👍🏻

B-tree와 B+ tree의 차이점

B-Tree와 B+Tree는 데이터베이스 시스템과 파일 시스템에서 널리 사용되는 자료구조입니다. 두 구조 모두 균형 잡힌 트리 구조를 가지고 있지만, 몇 가지 중요한 차이점이 있습니다. 주요 차이점을 설명해 드리겠습니다:

데이터 저장 위치
- B-Tree: 모든 노드(내부 노드와 리프 노드)에 키와 데이터를 저장합니다.
- B+Tree: 내부 노드에는 키만 저장하고, 모든 데이터는 리프 노드에 저장합니다.
- → 왜 B+Tree가 더 좋을까? 궁금’s
- → 아마? 키를 먼저 탐색을 쫙 하고, 최소한의 페이지에 실제 접근을 하는게 더 이득이니까? 키를 더 많이 가지고 있을 수 있으니까(누가? 메모리가)
리프 노드 연결
- B-Tree: 리프 노드들 사이에 연결이 없습니다.
- B+Tree: 모든 리프 노드가 링크드 리스트 형태로 서로 연결되어 있습니다.
검색 효율성
- B-Tree: 검색 시 루트에서 리프까지 내려가지 않아도 될 수 있어, 때때로 더 빠른 검색이 가능합니다.
- B+Tree: 항상 리프 노드까지 내려가야 하므로, 단일 검색의 경우 B-Tree보다 느릴 수 있습니다.
범위 검색
- B-Tree: 범위 검색 시 트리를 여러 번 탐색해야 할 수 있습니다.
- B+Tree: 리프 노드가 연결되어 있어 범위 검색이 매우 효율적입니다.
공간 활용
- B-Tree: 내부 노드에도 데이터를 저장하므로 B+Tree보다 적은 노드로 같은 양의 데이터를 저장할 수 있습니다.
- B+Tree: 내부 노드에 키만 저장하므로 더 많은 키를 저장할 수 있어 트리의 높이가 낮아질 수 있습니다.
- → 오~
삭제 연산
- B-Tree: 삭제 연산이 B+Tree보다 복잡할 수 있습니다.
- B+Tree: 모든 데이터가 리프 노드에만 있어 삭제 연산이 비교적 간단합니다.

일반적으로 B+Tree는 데이터베이스 인덱싱에 더 자주 사용되며, 특히 범위 검색이 빈번한 경우에 유리합니다.

B-Tree는 파일 시스템이나 데이터의 빈번한 검색과 삽입이 필요한 경우에 적합할 수 있습니다.

→ 호눅스왈: 사실상 B Tree라고 말하면 거의 B+Tree다~ (🎓박사님 말씀이니까 신뢰100)

Clustered Index란?

Clustered Index의 동작방식

클러스터 인덱스는 PK를 key로 가지고, 무조건 리프노드에는 실제 테이블 데이터를 가지고 있다..?
- 데이터는 PK에 따라 물리적으로 순서대로 저장
- PK가 없는 경우: UK, 내부에서 자동으로 생성된 값 순으로 사용
세컨더리 인덱스의 리프노드는 클러스터 인덱스를 가리킴
- 인덱스 도 지정된 키에따라 정렬됨 (ASC, DESC 지정 가능)
세컨더리 인덱스 탐색 과정은 → 세컨더리 키 → 클러스터링 키 → 실제 테이블?

클러스터 인덱스 (Clustered Index):
- 정의: 테이블당 하나만 존재할 수 있으며, 테이블의 물리적 순서를 결정합니다.
- 키: 일반적으로 Primary Key (PK)를 사용합니다.
- 구조:
  - 리프 노드에는 실제 테이블의 모든 데이터가 저장됩니다.
  - 데이터는 PK 값에 따라 물리적으로 정렬되어 저장됩니다.
- PK가 없는 경우:
  - Unique Key (UK)를 사용하거나,
  - 시스템이 자동으로 숨겨진 클러스터 키를 생성합니다.
- 장점: PK를 기준으로 한 검색이 매우 빠릅니다.
세컨더리 인덱스 (Secondary Index / Non-Clustered Index):
- 정의: 테이블에 여러 개 존재할 수 있는 추가적인 인덱스입니다.
- 구조:
  - 리프 노드에는 인덱스 키 값과 해당 레코드의 클러스터 인덱스 키 (또는 포인터)를 저장합니다.
  - 인덱스 키에 따라 정렬됩니다 (ASC 또는 DESC 지정 가능).
- 특징:
  - 실제 데이터는 포함하지 않고, 클러스터 인덱스를 가리킵니다.
  - 클러스터 인덱스와 독립적으로 정렬됩니다.
세컨더리 인덱스 탐색 과정:
1. 세컨더리 인덥스 키를 사용해 세컨더리 인덱스를 검색합니다.
2. 세컨더리 인덱스의 리프 노드에서 클러스터링 키(PK)를 얻습니다.
3. 클러스터링 키를 사용해 클러스터 인덱스를 검색합니다.
4. 클러스터 인덥스의 리프 노드에서 실제 테이블 데이터에 접근합니다.
추가 정보:
- 클러스터 인덱스는 데이터의 물리적 순서를 결정하므로, 데이터 삽입/수정/삭제 시 재정렬이 필요할 수 있어 오버헤드가 발생할 수 있습니다.
- 세컨더리 인덱스는 추가적인 공간을 사용하지만, 다양한 검색 조건에 대해 빠른 접근을 제공합니다.
- 인덱스 선택 (Index Selection)은 쿼리 최적화에 중요한 역할을 합니다. 데이터베이스 시스템은 여러 인덥스 중 가장 효율적인 것을 선택합니다.
성능 고려사항:
- 클러스터 인덅스는 범위 검색에 매우 효율적입니다.
- 세컨더리 인덱스는 등가 검색에 효과적이지만, 많은 수의 행을 검색할 때는 비효율적일 수 있습니다.
- 인덱스가 많을수록 검색 속도는 향상되지만, 삽입/수정/삭제 작업의 부하가 증가합니다.

이러한 인덱스 구조는 데이터베이스의 성능을 크게 향상시키지만, 적절한 설계와 관리가 필요합니다. 특정 데이터베이스 시스템이나 더 자세한 내용에 대해 알고 싶으시다면 추가로 질문해 주세요.

테이블을 저장하는 다른 방식도 있을까?

비클러스터드 인덱스 (Non-Clustered Index)

설명: 비클러스터드 인덱스는 테이블의 데이터와는 별도로 인덱스가 저장됩니다. 인덱스는 테이블의 데이터에 대한 포인터를 포함하고 있으며, 데이터가 물리적으로 정렬되지 않고 저장됩니다. 특징: 하나의 테이블에 여러 개의 비클러스터드 인덱스를 만들 수 있습니다. 검색 성능을 향상시키지만, 인덱스와 데이터를 유지하기 위해 추가적인 저장 공간이 필요합니다.

힙 (Heap)

설명: 힙은 기본적으로 테이블의 데이터가 물리적으로 순서 없이 저장되는 방식입니다. 인덱스가 없는 경우, 데이터는 삽입된 순서대로 저장됩니다. 특징: 데이터의 순서가 중요하지 않거나 특정 정렬이 필요하지 않을 때 사용됩니다. 검색 성능이 낮을 수 있지만, 데이터 삽입과 삭제가 빠를 수 있습니다.

인버티드 인덱스 (Inverted Index)

설명: 주로 텍스트 검색 시스템에서 사용됩니다. 인버티드 인덱스는 단어와 단어가 등장하는 문서 또는 레코드를 매핑합니다. 특징: 텍스트 검색 쿼리에서 효율적입니다. 대량의 텍스트 데이터에서 검색 성능을 크게 향상시킬 수 있습니다.

비트맵 인덱스 (Bitmap Index)

설명: 비트맵 인덱스는 각 열의 값에 대해 비트맵을 사용하여 인덱스를 만듭니다. 각 비트는 특정 값의 존재를 나타냅니다. 특징: 데이터의 카디널리티(유일한 값의 수)가 낮은 경우에 유용합니다. 주로 데이터 웨어하우스와 OLAP 시스템에서 사용됩니다.

R-트리 (R-Tree)

설명: R-트리는 공간 데이터의 색인에 사용됩니다. 주로 지리적 데이터와 같은 다차원 데이터의 검색에 적합합니다. 특징: 공간 쿼리(예: 범위 검색)에서 효율적입니다. 주로 GIS(지리 정보 시스템)에서 사용됩니다.

B+ 트리 (B+ Tree)

설명: B+ 트리는 B-트리의 변형으로, 모든 데이터가 리프 노드에만 저장되고, 내부 노드는 단지 데이터의 위치를 인덱스합니다. 특징: 범위 검색에 유리하고, 데이터베이스와 파일 시스템에서 자주 사용됩니다.

컬럼 기반 저장 (Columnar Storage)

설명: 데이터를 행이 아니라 열 단위로 저장합니다. 주로 OLAP(온라인 분석 처리) 시스템에서 사용됩니다. 특징: 특정 열의 데이터에 대해 빠른 집계 및 분석이 가능합니다. 대량의 데이터 처리와 분석에서 유리합니다.

압축 인덱스 (Compressed Index)

설명: 데이터와 인덱스의 저장 공간을 줄이기 위해 압축 기술을 사용합니다. 특징: 저장 공간을 절약하고, 대량의 데이터 처리에서 성능을 향상시킬 수 있습니다. 데이터 압축과 관련된 처리 비용이 발생할 수 있습니다.

물리적으로 테이블을 저장하는 다양한 방법

힙 테이블(메모리 스토리지 엔진): 작동 방식: 테이블은 기본적으로 해시 인덱스를 사용하여 메모리에 완전히 저장됩니다(B-트리도 가능함). 데이터가 메모리에 저장되므로 힙 테이블은 매우 빠른 데이터 액세스를 제공하지만 휘발성이므로 서버가 다시 시작되면 데이터가 손실됩니다. 사용 사례: 임시 또는 임시 데이터로, 빠른 검색을 위해 자주 액세스하는 데이터를 캐싱합니다.

B-트리 인덱싱(MyISAM, InnoDB): 작동 방식: 데이터는 B-트리라는 구조에 저장됩니다. 여기서 트리의 각 노드는 여러 하위 노드를 가질 수 있습니다. B-트리는 균형이 잡혀 있습니다. 즉, 조회, 삽입 및 삭제가 효율적이도록 트리의 높이가 상대적으로 짧게 유지됩니다. 사용 사례: 데이터의 빠른 검색 및 수정이 필요한 범용 스토리지입니다.

해시 인덱싱(MEMORY, NDB): 작동 방식: 데이터는 키 값의 해시를 기반으로 저장됩니다. 이를 통해 매우 빠른 조회가 가능하지만 범위 쿼리는 데이터가 정렬된 순서로 저장되지 않기 때문에 비효율적입니다. 사용 사례: 세션 ID로 사용자 세션을 조회하는 등 정확한 일치가 필요한 상황입니다.

다른 시스템의 IOT(인덱스 구성 테이블): 작동 방식: InnoDB의 클러스터형 인덱스와 유사하게 일부 데이터베이스 시스템(예: Oracle)은 테이블 데이터가 B-Tree 인덱스 구조에 저장되는 IOT(인덱스 구성 테이블)를 지원합니다. 차이점은 전체 테이블이 인덱스의 일부로 저장된다는 것입니다. 사용 사례: 쿼리에 기본 키 조회가 자주 포함되는 경우 기본 키를 기준으로 데이터를 정렬하면 성능 이점을 얻을 수 있습니다.

컬럼형 스토리지(MySQL에 기본 제공되지 않지만 MySQL HeatWave에서 지원됨): 작동 방식: 데이터는 행이 아닌 열을 기준으로 저장되므로 일반적으로 대규모 데이터 세트에 대한 집계와 관련된 분석 쿼리 속도를 크게 높일 수 있습니다. 사용 사례: 특정 열에 대한 읽기 성능이 행 기반 트랜잭션보다 더 중요한 데이터 웨어하우징, OLAP(온라인 분석 처리).

로그 구조 병합 트리(LSM-트리)(RocksDB와 같은 시스템에서 사용됨): 작동 방식: 데이터는 SSTable이라고 하는 일련의 정렬된 파일에 저장되며 레벨별로 구성됩니다. LSM 트리는 쓰기가 많은 워크로드 및 일괄 처리에 최적화되어 있습니다. 사용 사례: 삽입 및 업데이트 패턴이 많은 로깅 시스템이나 애플리케이션과 같은 처리량이 높은 쓰기 작업입니다.

테이블당 파일 테이블스페이스(InnoDB): 작동 방식: InnoDB는 공유 테이블스페이스가 아닌 자체 테이블스페이스 파일에 각 테이블을 저장하는 것을 지원합니다. 이렇게 하면 개별 테이블의 관리, 백업 및 복구가 더 쉬워집니다. 사용 사례: 유지 관리 또는 성능상의 이유로 테이블 격리가 필요한 데이터베이스.

공유 테이블스페이스(InnoDB): 작동 방식: 여러 테이블이 공통 테이블스페이스 파일을 공유합니다. 이는 모든 테이블과 인덱스가 단일 파일 또는 파일 세트에 함께 저장되는 InnoDB가 원래 설계된 방식입니다. 사용 사례: 각 테이블에 대한 개별 파일을 관리할 필요가 없는 작은 테이블이 많은 시스템입니다.

압축 테이블(InnoDB): 작동 방식: 테이블은 압축 형식으로 저장되므로 읽기 및 쓰기 중 데이터 압축 및 압축 해제를 위해 추가 CPU 사용량을 사용하여 디스크 공간 사용량을 줄입니다. 사용 사례: 디스크 공간이 부족하고 압축 성능 비용이 허용되는 대규모 데이터 세트입니다.

MySQL과 InnoDB

InnoDB 란 무엇인가?

InnoDB는 MySQL에서 가장 인기 있고 널리 사용되는 스토리지 엔진 중 하나로, 대용량 데이터를 처리하고 높은 성능, 안정성 및 확장성을 제공하도록 설계되었습니다.
MySQL 5.5부터 기본 스토리지 엔진
트랜잭션 처리 지원 (커밋, 롤백)
행 단위로 Lock을 걸 수 있다.
FK 지원
버퍼풀
클러스터링 인덱스
MVCC

InnoDB 에서 create database -> create table 을 할 때 일어나는 일을 설명해 보세요.

CREATE DATABASE 실행: a. 파일 시스템에 데이터베이스 디렉토리 생성:
- MySQL 데이터 디렉토리 아래에 새로운 디렉토리가 생성됩니다.
- 디렉토리 이름은 데이터베이스 이름과 동일합니다.
b. 메타데이터 업데이트:
- information_schema 데이터베이스의 SCHEMATA 테이블에 새 데이터베이스 정보가 추가됩니다.
c. 권한 설정:
- 새로운 데이터베이스에 대한 기본 권한이 설정됩니다.
CREATE TABLE 실행: a. 테이블 정의 파싱:
- SQL 문장이 파싱되어 테이블 구조가 분석됩니다.
b. 테이블 메타데이터 생성:
- information_schema 데이터베이스의 TABLES, COLUMNS 등의 테이블에 새 테이블 정보가 추가됩니다.
c. InnoDB 테이블스페이스 할당:
- 테이블을 위한 새로운 테이블스페이스가 할당됩니다. (file-per-table 설정인 경우)
- .ibd 파일이 생성됩니다. (데이터베이스_이름/테이블_이름.ibd)
d. 테이블 구조 파일 생성:
- .frm 파일이 생성되어 테이블 구조 정보를 저장합니다. (MySQL 5.7 이전 버전)
- MySQL 8.0부터는 데이터 딕셔너리에 저장됩니다.
e. 인덱스 생성:
- PRIMARY KEY나 기타 정의된 인덱스를 위한 B-Tree 구조가 초기화됩니다.
f. 시스템 테이블 업데이트:
- InnoDB의 내부 시스템 테이블들이 업데이트됩니다.
g. 트랜잭션 로그 기록:
- 테이블 생성 작업이 리두(redo) 로그에 기록됩니다.
h. 버퍼 풀 초기화:
- 새 테이블을 위한 버퍼 풀 페이지가 필요에 따라 할당됩니다.

InnoDB 외에 어떤 스토리지 엔진들을 사용할 수 있는가? 특징은?

MYISAM
MEMORY
CSV
NDB

Indexing

MySQL 에서 지원하는 인덱스의 종류와 용도에 대해 설명해 보세요

MySQL 로 지도정보를 저장하고 싶습니다. 어떻게 해야 할까요?

데이터베이스 일반

📚 도서를 추천해주세요

🎸 기타

기타 유용한 학습 링크

Provide feedback

Saved searches

Use saved searches to filter your results more quickly