2025-09-07

오늘 배운 것

8.3 B-Tree 인덱스

• B-Tree
  • 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고 가장 먼저 도입된 알고리즘
  • 아직까지 가장 범용적인 목적으로 사용
  • 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지

8.3.1 구조 및 특성

• 트리구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어 있는 형태
• 리프 노드 : 가장 하위에 있는 노드
• 브랜치 노드 : 루트노드도 아니고 리프노드도 아닌 중간의 노드
• 인덱스의 리프노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있음
• 인덱스는 테이블의 키 칼럼만 가지고 있음
  • 따라서 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야함
• InnoDB 스토리지 엔진의 B-Tree 인덱스
  • 프라이머리 키가 ROWID 역할을 함
  • 세컨더리 인덱스를 통해 데이터 파일의 레코드를 찾아감
  • InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때 데이터 파일을 바로 찾아가지 못함
    • 인덱스에 저장되어있는 프라이머리 키 값을 이용해 프라이머리 키 한번 더 검색
    • 그 후 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽음
    • 즉, 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽이 위해 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색 해야됌

8.3.2 B-Tree 인덱스 키 추가 및 삭제

8.3.2.1 인덱스 키 추가

• 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있음
• 키 추가 방식
  • B-Tree에 저장될 때 저장될 키 값을 이용해 적절한 위치를 검색
  • 레코드의 키값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장
  • 리프 노드가 꽉차서 더 저장 불가 시, 리프 노드가 분리되고 상위 브랜치 노드까지 처리의 범위가 넓어짐
• InnoDB 키 추가 방식
  • 프라이머리 키나 유니크 인덱스의 경우는 중복 체크가 필요하여 즉시 B-Tree에 추가하거나 삭제
  • 이 외의 인덱스는 추가 작업을 지연시켜 나중에 처리 가능

8.3.2.2 인덱스 키 삭제

• 키 값이 저장된 B-Tree의 리프 노드르 찾아 그냥 삭제 마크
• 삭제 마킹된 인덱스 키공간은 계속 방치하거나 재활용 가능
• 마킹 작업도 디스크 I/O 필요
• InnoDB에서 키 삭제도 버퍼링 되어 지연 처리 가능

8.3.2.3 인덱스 키 변경

• 저장될 인덱스 키 값에 따라 저장될 위치가 결정되기 때문에 단순한 값 변경은 불가함
• 그냥 그 키를 삭제하고 다시 새로운 키값을 추가하는 형태로 작동

8.3.2.4 인덱스 키 검색

• B-Tree 인덱스르 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우 사용 가능
• 부등호 비교조건에서도 인덱스 활용가능
  • 이분 탐색으로 시작 지점 찾고 그 부분부터 범위 탐색
• 인덱스를 구성하는 키값의 뒷부분만 검색하는것은 사용 불가
  • 예 %abc → 이경우는 데이터가 왼쪽 기준 정렬이기 때문에 데이터가 산개 되어있음
• 인덱스의 키 값에 변형이 가해진 후 비교되는 경우는 사용 불가
  • 함수나 연산을 수행한 결과로 정렬 또는 검색은 불가