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

B+ 트리 인덱싱

B-tree 의 등장 배경

Boeing Research Labs에서 근무하는 Rudolf Bayer와 Edward M. McCreight가 대규모의 random-access 파일의 인덱스 페이지를 효율적으로 관리할 목적으로 발명

발명한 사람들은 B-tree의 B가 무엇을 의미하는지 설명하지 않았다. → B가 무엇을 의미하는지 더 많이 고민하면 B-tree를 더 잘 이해할 수 있다고 말했다.

B-tree 의 동작 방식

B-Tree Visualization

• 검색

  이진 트리와 유사 → 루트에서 시작해 위에서 아래로 재귀적으로 탐색

• 삽입

  

  루트노드에서 탐색을 시작해 리프 노드까지 내려간 후 삽입을 시작

  트리를 검색해 새 요소를 추가해야 하는 리프 노드를 찾는다. 그리고 아래의 단계를 따른다.

  1. 하나의 노드에 허용되는 최대 요소의 개수보다 적은 수의 요소가 포함되어 있으면 새로운 요소를 넣을 수 있다. 노드의 요소 순서를 유지하면서 노드에 새로운 요소를 삽입한다.
  2. 만약 노드에 허용되는 최대 요소 수만큼 꽉 차있다면
     1. 단일 중앙값은 리프 노드와 삽입되는 새요소 중에서 선택
     2. 중앙값보다 작은 값은 새로운 왼쪽 노드에 배치되고, 중앙값보다 큰 값은 새로운 오른쪽 노드에 배치되며 중앙값은 분리 값으로 사용
     3. 분리 값은 노드의 상위 노드에 삽입되며 이로 인해 노드가 분할될 수 있다. 노드에 부모가 없으면 해당 노드 위에 새 루트를 생성

B-tree와 B+ tree의 차이점

B+ tree의 동작 방식

B+ Tree Visualization

	B-tree	B+ tree
포인터	모든 노드에 데이터 포인터 존재	리프 노드에만 데이터 포인터 존재
검색	리프에서는 모든 키를 사용할 수 없어 더 많은 시간이 걸리는 경우가 많다.	모든 키는 리프 노드에 있어 검색이 더 빠르고 정확해진다.
중복 키	키의 중복은 트리에 유지되지 않는다.	중복된 키가 유지되고 모든 노드가 리프에 존재한다.
삽입	삽입에는 시간이 더 걸린다.	삽입이 더 쉽고 결과가 항상 동일하다.
삭제	내부 노드를 삭제하는 것은 매우 복잡하며 많은 변형을 거친다.	모든 노드가 리프에서 발견되므로 노드 삭제가 쉽다.

Clustered Index란?

• 정의
  • 테이블의 데이터를 지정 컬럼 기준으로 물리적으로 정렬한 인덱스
• 특징
  • 테이블 당 하나만 존재
  • 지정 컬럼이 없을 경우 기본 키로 자동 생성
• Clustered Index의 동작방식
  • 논리프 페이지는 자식 페이지의 주소를, 리프 페이지에 실제 데이터를 저장
  • 지정 컬럼을 기준으로 리프 페이지들이 정렬해서 보관
  • 데이터 입력, 수정, 삭제시에도 정렬을 유지
  • 순차 접근, 범위 쿼리에 효과적이다
• 테이블을 저장하는 다른 방식도 있을까?
  • non-clustered index
    • 리프에 실제 데이터 페이지 주소와 페이지안 오프셋을 갖고 있다
• 물리적으로 테이블을 저장하는 다양한 방법
  • 페이지 기반 저장
    • 고정 크기로 데이터를 나눠 저장
  • 파일 구조

MySQL과 InnoDB

• InnoDB 란 무엇인가?
  • mysql 5.5.5(2010년) 이후 버전에서 사용하는 기본 스토리지 엔진이다.
    • 스토리지 엔진이란?
      • 데이터베이스 엔진(또는 스토리지 엔진)은 데이터베이스 관리 시스템(DBMS)이 데이터베이스에서 데이터를 생성, 읽기, 업데이트 및 삭제(CRUD)하는 데 사용하는 기본 소프트웨어 구성 요소(컴포넌트)이다.
  • InnoDB의 주요 장점
    • DML 작업은 사용자 데이터를 보호하기 위해 커밋, 롤백 및 충돌 복구 기능을 갖춘 트랜잭션을 사용하는 ACID 모델을 따릅니다.
    • Row-level locking과 Oracle-style 일관성 읽기는 멀티 유저 동시성 및 성능을 향상 시킨다.
    • InnoDB 테이블은 기본 키를 기반으로 쿼리를 최적화하기 위해 디스크의 데이터를 정렬합니다. 각 InnoDB 테이블에는 기본 키 조회에 대한 I/O를 최소화하기 위해 데이터를 구성하는 클러스터형 인덱스라는 기본 키 인덱스가 있습니다.
    • 데이터 무결성을 유지하기 위해 InnoDB는 FOREIGN KEY 제약 조건을 지원합니다. 외래 키를 사용하면 삽입, 업데이트 및 삭제가 검사되어 관련 테이블 간에 불일치가 발생하지 않는지 확인됩니다.
• InnoDB 에서 create database -> create table 을 할 때 일어나는 일을 설명해 보세요.
  • create database ⇒ 시스템 테이블스페이스에 데이터베이스 정보를 기록하고 데이터베이스에 해당하는 디렉토리가 생성된다.(일반적으로 MySQL 데이터 디렉토리 하위)
  • create table ⇒
    • 테이블 메타데이터 생성
      • 테이블 구조 정보를 InnoDB 데이터 딕셔너리에 저장
    • 테이블스페이스 생성
      • .ibd파일 생성
      • 이 파일은 데이터베이스 디렉토리 내에 생성됨
    • 테이블 구조 초기화
      • B-Tree 인덱스 구조 초기화 (클러스터드 인덱스)
    • UNDO 로그 공간 할당
      • 트랜잭션 롤백을 위한 UNDO 로그 공간 준비
    • 트랙잭션 로그 기록
      • 테이블 생성 작업에 대한 로그 기록
• InnoDB 외에 어떤 스토리지 엔진들을 사용할 수 있는가? 특징은?
  • MyISAM
    • 정적인 데이터를 저장하고 자주 읽기 작업이 일어나는 테이블에 적합하다.
    • MySQL 5.5.5 버전 이전에 사용한 기본 스토리지 엔진이다.
    • 테이블 설치 공간이 작다.
    • 테이블 수준 잠금은 읽기/쓰기 작업 부하의 성능을 제한하므로 웹 및 데이터 웨어하우징 구성에서 읽기 전용 또는 대부분 읽기 작업 부하에 자주 사용됩니다.
  • MEMORY
    • 메모리에 데이터를 저장하는 엔진.
    • Transaction을 지원하지 않고 table-level locking을 사용한다.
    • 메모리를 사용하기 때문에 기본적으로 속도가 아주 빠른 편이지만 데이터를 읽어버릴 위험이 있다. → 그렇기 때문에 중요하지 않지만 빠른 처리가 필요한 임시 테이블로 많이 사용하는 편이다.
    • 메모리 테이블의 모든 데이터는 메모리 안에 저장되므로 쿼리가 디스크 입출력을 기다릴 필요가 없다.
    • HEAP 테이블이라 불리던 메모리 테이블은 불변하는 데이터나 재시작 이후 지속되지 않는 데이터에 빠르게 접근하는 데 유용하다. 메모리 테이블의 테이블 구조는 서버가 재시작해도 지속되지만 데이터는 지속되지 않는다.
  • CSV
    • 해당 테이블은 실제로 쉼표로 구분된 값이 포함된 텍스트 파일이다.
    • CSV 테이블을 사용하면 CSV 형식으로 데이터를 가져오거나 덤프하여 동일한 형식을 읽고 쓰는 스크립트 및 애플리케이션과 데이터를 교환할 수 있다.
    • CSV 테이블은 인덱싱되지 않기 때문에 일반적으로 일반 작업 중에는 InnoDB 테이블에 데이터를 유지하고 가져오기 또는 내보내기 단계에서는 CSV 테이블만 사용합니다.
  • 이외에도 Archive, Blackhole, NDB, Merge 등등 여러 엔진이 존재합니다.

스토리지 엔진 기능 요약 표

출처 : https://dev.mysql.com/doc/refman/8.4/en/innodb-introduction.html

Indexing

• MySQL 에서 지원하는 인덱스의 종류와 용도에 대해 설명해 보세요.
  • B-Tree 인덱스
    • 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다.
    • B-Tree는 이진이 아니라 “Balanced”이다! (아니다… B는 생각하기 나름이다)
    • 전체 일치 또는 좌측 일부 일치와 같은 검색만 가능하다.
  • R-Tree 인덱스
    • 2차원 데이터를 인덱싱하고 검색하는 목적의 인덱스다.
    • 기본 내부 매커니즘은 B-Tree와 흡사한다.
  • 전문 검색 인덱스
    • 전문(Full Text) 검색에는 B-Tree인덱스를 사용할 수 없다.
    • 문서 전체에 대한 분석과 검색을 위한 인덱스이다.
    • 일반화된 기능의 명칭이지 전문 검색 알고리즘의 이름을 지칭하는 것은 아니다.
  • 함수 기반 인덱스
    • 일반적인 인덱스는 칼럼의 값 일부 또는 전체에 대해서만 인덱스 생성이 허용된다.
    • 칼럼의 값을 변형해서 만들어진 값에 대해 인덱스를 구축해야 할 때도 있다.
    • 가상 칼럼을 이용한 인덱스 vs 함수를 이용한 인덱스
• MySQL 로 지도정보를 저장하고 싶습니다. 어떻게 해야 할까요?
  • POINT를 사용하여 위도와 경도를 저장한다.
  • SPATION INDEX()를 사용하여 R-Tree 인덱스를 이용해 다양한 값들을 처리할 수 있게 한다.

데이터베이스 일반

• Oracle, MS-SQL, PostgreSQL 에서 테이블과 레코드를 저장하는 방식은 어떤 것들이 있는가?
• 그룹으로 위 주제에 대해 학습하고 학습정리결과를 댓글로 달아 주세요.

## **B+ 트리 인덱싱**