B-Tree 인덱스
인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘 입니다.
지금까지도 가장 범용적인 목적으로 사용되고 있는 인덱스 알고리즘 입니다.
B-Tree의 B가 바이너리(이진) 트리라고 잘못 생각할 수 있겠지만,
B는 Balanced를 의미한다는 점을 주의해야 합니다.
B-Tree는 컬럼의 원래 값을 변형 시키지 않고 (물론 값의 앞부분만 잘라서 관리 함),
인덱스 구조체 내에서는 항상 정렬된 상태로 유지합니다.
하지만 실제 데이터 파일의 경우에는 정렬되어 있지 않고 임의의 순서로 저장되어 있습니다.
레코드가 삭제 되고 빈 공간이 생기면 다음 INSERT는 가능한 공간을 재활용 할 수 있도록
DBMS가 설계되어 있기 때문에 항상 순서대로 저장되는 것은 아닙니다.
구조 및 특성
- Root node
- 최상위에 있는 하나의 루트 노드
- Leaf node
- 루트의 하위 자식 노드
- 실제 데이터 레코드를 찾아가기 위한 주소 값
- Branch node
- 루트도 리프도 아닌 중간의 노드
B-Tree 인덱스 키 추가 및 삭제
인덱스 키 추가
새로운 키 값이 B-Tree에 저장될 때는 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고, 그렇지 않을 수도 있습니다.
- MyISAM, MEMORY 스토리지 엔진 : INSERT 실행 → 즉시 새로운 키 값 반영
- InnoDB : 필요시에 인덱스 키 추가 작업을 지연 가능 (But. Primary Key, Unique Index의 경우에는 중복체크가 필요해 즉시 반영)
B-Tree에 저장될 때는 저장될 키 값을 이용해서 B-Tree상의 적절한 위치를 검색해야 합니다.
저장될 위치가 결정되면 키 값과 대상 레코드의 주소 정보를 B-Tree 리프노드에 저장하게 되는데,
리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리되어야 하는데,
이는 상위 브랜츠 노드까지 처리 범위가 넓어집니다.
이러한 작업으로 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 들게 됩니다.
인덱스 키 삭제
B-Tree 리프 노드를 찾아 삭제 마크 하면 끗 (가장 간단)
인덱스 키 변경
B-Tree의 키 값 변경은 먼저 키 값을 삭제 후, 다시 추가하는 순서로 진행
인덱스 키 검색
위의 INSERT, DELETE, UPDATE 작업의 추가 비용을 감당하면서 인덱스를 구축하는 이유가 바로
빠른 검색을 위해서 입니다.
트리 탐색
: 루트 노드 → 브랜치 노드 → 리프 노드 까지 이동하면서 비교 작업을 수행
B-Tree 인덱스의 검색은 100% 일치 하거나 갚의 앞부분이 일치하는 경우에만 사용할 수 있습니다.
또한 인덱스 키값이 변형이 된다면 B-Tree의 빠른 검색을 사용할 수 없습니다.
InnoDB 스토리지 엔진의 테이블에서는 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한
인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있습니다.
따라서 UPDATE, DELETE 실행이 될 때 테이블에 적절하게 사용할 수 있는 인덱스가 없으면,
불필요하게 많은 레코드를 잠그게 되고, 모든 레코드를 잠글 수도 있습니다.
→ InnoDB 에서는 그만큼 인덱스의 설계가 중요합니다…????????????? 뭔소리지
인덱스 키 값의 크기
B-Tree는 자식 노드를 몇개까지 가질 수 있을까요? 🤔
인덱스의 페이지 크기와 키 값 크기에 따라 결정 됩니다.
인덱스 페이지의 크기 기본값은 16KB 입니다. (MySQL 5.7 부터 4~16KB 변경 가능)
자식노드의 경우에는 종류별로 6-12바이트까지 다양한 값을 가질 수 있습니다.
키 값이 16바이트인 경우에는 한 페이지에 몇개의 키를 저장할 수 있는지 알아보면…
16 * 1024 / (16 + 12) = 585
이 경우에는 하나의 페이지에 자식 노드를 585개를 가질 수 있는 B-Tree가 됩니다.
하지만 인덱스 키 값 두배로 커지면 어떻게 될까요?
16 * 1024 / (32 + 12) = 372
이 같은 경우에는 SELECT로 500개의 레코드를 읽어야 할 때 최소 2번 이상 디스크를 읽어야 합니다.
결국 키 값의 크기가 커지면 디스크로 읽어야 하는 횟수가 늘어나고 그만큼 느려지게 됩니다.
그리고 인덱스를 캐시해 두는 InnoDB, MyISAM의 키 캐시 영역은 크기가 제한적이기 때문에
이 또한 인덱스 크기가 커지면 커질수록 메모리의 효율이 떨어지게 됩니다.
B-Tree 또한 인덱스 키 값이 커지면 커질 수록 B-Tree의 깊이가 깊어져서 비효율적이게 됩니다.