[MySQL] [1]인덱스(Index)란-B-Tree?

 

 

MySQL의 인덱스(Index)-B-Tree를 알아보자

 

 

인덱스란?

인덱스는 값을 찾기 편리하게 만들어주는 도구입니다. 쉽게 비유하자면 책의 마지막 부분에 있는 찾아보기 페이지가 인덱스와 비슷합니다. 자바의 컬렉션을 예로 들어보면, SortedList와 ArrayList가 있습니다. SortedList는 저장된 값을 항상 정렬된 상태로 유지하는데, 이는 찾아보기에서 "ㄱ", "ㄴ", "ㄷ"와 같이 정렬된 것과 유사합니다. 그러나 SortedList는 데이터가 저장될 때 항상 정렬된 값을 가져야 하므로 저장 과정이 복잡하고 속도가 느릴 수 있지만, 조회 과정은 매우 빠르게 동작합니다. 반면에 ArrayList는 값을 저장하는 순서를 그대로 유지하는 구조입니다.

DBMS의 인덱스는 SortedList를 사용하고, 데이터 파일은 ArrayList와 같은 자료구조로 저장됩니다. 이를 통해 데이터에 효율적으로 접근할 수 있습니다.

 

데이터 저장방식은 두가지정도로 구분됩니다. B-Tree 인덱스와 Hash 인덱스로 구분할 수 있습니다.

• B-Tree 알고리즘 : 가장 일반적으로 사영되는 인덱스 알고리즘으로, 칼럼의 값을 변경하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘이다.
• Hash 알고리즘 : 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘으로, 매우 빠른 검색을 지원한다.

---

 

B-Tree 인덱스

데이터베이스에의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되는 알고리즘이다. B-Tree에서의 'B'는 Binary(이진)의 B가 아닌 "Balanced"를 의미한다. B-Tree인덱스는 칼럼의 원래값을 변경하지 않고 인덱스 구조체 내에서는 항상 정렬된 상태로 유지한다.

 

구조 및 특성

B-Tree의 기본구조

• 루트노드(Root node)  : 가장 상위에 위치하는 노드, 일반적으로 하나의 노드를 갖는다.
• 브랜치 노드 (Branch Node) : 브랜치 노드는 키(key)와 해당 키가 가리키는 자식 노드에 대한 포인터를 포함합니다. 트리를 탐색하는데 경로를 형성한다.
• 리프노드(Leaf Node) : 가장 하위에 위치하는 노드들로 실제 데이터를 찾아갈 수 있는 주소값을 가지고 있어 주소 값을 이용해 데이터파일에서 데이터를 조회한다.

 

 

MyISAM엔진과 InnoDB엔진의 차이

 

MyISAM엔진은 리프노드에서 프라이머리키로 값을 찾는 것이 아닌 레코드 주소로 찾는다."레코드주소는" MyISAM테이블의 생성 옵션에 따라 레코드가 테이블에 INSERT 된 순번에 따른 위치(Offset)이다. 즉 그래서 프라이머리 키로 찾아가는 것이 아닌 생성 었을 때 만들어진 레코드 주소를 찾는다.

반면

InnoDB엔진은 리프노드에서 프라이머리 키로 데이터를 찾는 과정을 거치게 된다. 즉 InnoDB엔진을 사용한 테이블을 만들 때에는 프라이머리 키를 명시적으로 지정해줘야 한다.

 

인덱스 키 추가, 삭제, 변경, 검색

추가하는 과정은 많은 비용을 초래하게 된다. 리프노트에 저장공간이 꽉 차게 되면 분리해야 하는 과정을 거치게 되는데 분리하는 과정이 비용이 많이 발생하게 된다. 분리과정을 통해서 디스크의 I/O가 발생할 수 있기 때문이다. 하지만 InnoDB엔진을 사용하면 지연 처리라는 방법을 사용해 비용을 감소할 수는 있다.

삭제는 과정은 정말 단순하다 삭제될 키는 리프 노드에서 삭제되고, 해당 위치에 빈 공간이 남습니다. 이러한 빈 공간은 새로운 키가 삽입될 때 재사용될 수 있다.

검색하는 과정에서 UPDATE, INSERT, DELETE 작업을 할 때에도 인덱스를 사용하는 이유는 많은 양의 데이터를 빠르게 처리할 수 있기 때문입니다. B-트리의 구조를 통해 루트 노드부터 리프 노드까지 거쳐 비교 작업을 수행하는 "트리 탐색"을 실시합니다. 이를 통해 데이터베이스는 원하는 값을 빠르게 찾을 수 있습니다. 또한, 인덱스를 사용하여 검색할 때에는 100% 일치하는 값 또는 값의 앞부분 (Left-most part)만 일치하는 경우에만 사용할 수 있습니다. 즉, 뒷부분인 키 값만을 가지고는 검색을 할 수 없습니다. 이러한 특징은 검색을 보다 정확하고 빠르게 수행할 수 있도록 도와줍니다.

또한, InnoDB에서는 특별한 락(lock)을 사용하기 때문에 설계에 더욱 중요합니다. 이는 데이터의 일관성과 동시성을 보장하기 위해 필요한 작업으로, 데이터베이스의 안정성을 유지하는 데에 중요한 역할을 합니다. 따라서 데이터베이스의 성능과 안정성을 극대화하기 위해서는 인덱스를 효율적으로 사용하고 InnoDB 엔진의 특징을 잘 고려하여 설계해야 한다.

 

페이지

페이지(Page)는 InnoDB 엔진에서 디스크 데이터를 저장하는 가장 기본적인 단위이다. 페이지의 크기와 페이지의 포함된 키의 크기는 데이터베이스의 성능에 매우 중요한 영향을 미친다. 일반적으로 페이지의 크기는 대략 6~12바이트까지로 생성된다. 페이지의 크기가 커지고 키의 크기가 커지게 되면 디스크로 부터 읽어올수있는 양이 부족해 횟수가 증가하게되면서 여러번의 I/O를 하게되면서 메모리의 성능이 감소하게된다. 또한 페이지에 포함된 키의 크기가 커지게되면 페이지에 저장될 수 있는 키의 수가 줄어들게 되어 노드의 분리가 발생하게 되면서 메모리의 성능에 악영향을 끼치게 됩니다. 결국 페이지와 포함된 키의 크기는 디스크의 I/O 작업의 효율성을 결정하는 요소이기 때문에 잘 고려하여 설계를 해야 한다.

 

선택도(기수성)

선택도(기수성)는 모든 인덱스 키 값 중에서 유니크한 값의 수를 의미합니다. 예를 들어, 인덱스 키값이 1000개 있을 때 유니크한 키값이 12개라면 선택도는 12입니다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 빠르게 처리된다.

 

 

예시로 쇼핑몰의 카테고리를 생각해 보자.

1. 카테고리가 5(음식, 옷, 가전제품, 가구, 의류) 개일 때: 카테고리가 5개이므로 선택도는 5입니다. 예를 들어 음식 카테고리에서 햄버거를 찾는 경우, 전체 물건 중 음식 카테고리는 약 2000개의 물건만을 대상으로 검색됩니다. 그 후에 햄버거를 찾는 알고리즘이 실행됩니다.
2. 카테고리가 2(음식, 의류)개일 때: 카테고리가 2개이므로 선택도는 2입니다. 이 경우 음식 카테고리에서 햄버거를 찾는 경우, 전체 물건 중 음식 카테고리는 약 5000개의 물건을 대상으로 검색됩니다. 따라서 검색 속도가 첫 번째 예시에 비해 느릴 것입니다.

이와 같이 선택도에 따라 검색하는 성능이 차이가 나므로 선택도를 고려하여 인덱스를 설계하고 사용해야 합니다.

.

---

 

 

B-Tree 인덱스 데이터 읽기

 

인덱스 레인지 스캔

인덱스 레인지 스캔은 인덱스에서 특정 범위의 데이터를 검색하는 방법 중 가장 대표적인 방법 중 하나입니다. 브랜치 노드에서 시작 기준으로 해당 범위를 포함하는 리프 노드를 찾은 후에, 해당 리프 노드에서는 시작부터 끝 부분까지의 데이터를 모두 스캔하여 검색하는 방식입니다.

 

동작 방식

레인지 스캔 동작 방식

1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. 이를 인덱스 탐색(Index seek)라고 한다.
2. 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다. 이과정을 인덱스 스캔(Index scan)이라고 한다.
3. 인덱스 스캔으로부터 읽어 들인 인덱스 키와 레코드 주소를 통해 저장된 페이지를 가져오고 최종 레코드를 읽어온다.

필요에 따라 3번 과정은 필요하지 않을 수 있다. 이를 커버링인덱스 라고 한다. 커버링 인덱스로 처리되는 쿼리는 디스크의 레코드를 읽지 않아도 되기 때문에 랜덤 읽기가 줄어들며 성능이 향상된다.

 

인덱스 풀 스캔

레인지 스캔과는 다르게 리프노드의 인덱스를 처음부터 끝까지 읽는 방식을 인덱스 풀스캔이라고 한다. 쿼리가 인덱스에 명시된 칼럼만으로 저건을 처리할 경우 이방식을 사용한다. 레인지의 특정한 값을 찾는 것이 아닌 인덱스의 포함된 모든 데이터를 조회하는 방식이다.

동작 방식

리프노드의 인덱스 키 A부터 W까지 모든 데이터를 조회한다.

 

 

루스 인덱스 스캔

오라클과 같은 "인덱스 스킵 스캔"과 비슷하게 동작한다. 쉽게 말해 느슨하게 인덱스를 읽는 것을 말한다.

만약 MEMBER테이블에 프라이머리 키로 ID가 1,2,3,4가 있고 각 프라이머리 키에 데이터가 10개씩 있다고 가정하자

SELECT MIN(ID) FROM MEMBER WHERE ID BETWEEN 2 AND 4 GROUP BY ID로 데이터를 조회한다면 프라이머리 2인 데이터 10개 3인데이터 10개 4인데이터 10개를 조회한다. 하지만 루스 스캔을 사용하면 2의 첫 번째 데이터만 읽고 아래는 같다고 생각해 무시한다 이런 과정을 4까지 진행한다. 그리고 쿼리를 완료한후 값을 전달해 준다.

루스인 덱스 스캔은 GROUP BY를 사용할 때만 사용가능하다.

 

인덱스 스킵 스캔

인덱스 스킵 스캔(Index Skip Scan)은 인덱스의 일부를 건너뛰고(스킵) 나머지 부분을 스캔하여 데이터를 찾는 방법입니다. 일반적으로 다중 칼럼 인덱스가 있는 경우, 첫 번째 칼럼에 대한 조건이 주어지지만 두 번째 칼럼에 대한 조건이 주어지지 않은 경우에 사용됩니다.

CREATE TABLE Products (
    Category VARCHAR2(50),
    Subcategory VARCHAR2(50),
    ProductName VARCHAR2(100),
    Price NUMBER
);

CREATE INDEX idx_products_category_subcategory ON Products(Category, Subcategory);

다음과 같이 제품 테이블의 카테고리와 서브 카테고리를 활용한 인덱스를 생성했습니다. 

SELECT * FROM Products WHERE Category = 'Electronics' AND Subcategory = 'Laptops';

다음과 같이 Categorydhk Subcategory로 두 개의 조건을 통해서 검색을 하면 일반 인덱스 활용해서 Electronics의 Laptops를 찾습니다. 

SELECT * FROM Products WHERE Category = 'Electronics';

이렇게 Subcategory를 조건을 적용하지 않고 사용한다면 우리가 작성했던 인덱스를 통해 데이터를 조회할 수 없습니다. 하지만 MySQL 8.0 이상부터는 옵티마이저 힌트를 통해서 인덱스 스킵 스캔을 사용할 수 있습니다.

SET optimizer_switch='skip_scan=on' 를 활성화된 상태에서 사용한다면 인덱스 스킵 스캔을 사용할 수 있습니다.

 

---

 

B-Tree 인덱스 정렬 및 스캔 방향

MySQL 8.0 버전 이상부터는 인덱스 작성 혼합으로 오름차순과 내림차순을 사용할 수 있게 되었다.

CREATE INDEX ix_test ON Test (name ASC , password DESC);

혼합해서 사용가능

 

 

인덱스 스캔방향

SELECT * FROM MEMBER ORDER BY name DESC LIMIT 1

MySQL에서는 내림차순으로 정렬된 데이터를 가져올 때, 정확히 말하면 "위에서부터"가 아니라 "뒤에서부터" 데이터를 가져옵니다. 즉, 내림차순으로 정렬된 경우 MySQL은 인덱스의 끝부터 시작하여 역순으로 데이터를 스캔하며, 이를 내림차순 스캔 방향이라고 합니다. 그래서 내림차순으로 정렬된 경우, MySQL은 인덱스의 끝에서부터 시작하여 가장 큰 값을 찾아옵니다. 이후 LIMIT으로 지정한 개수만큼의 행을 찾아올 때까지 인덱스를 거꾸로 스캔합니다.

반면, 오름차순으로 정렬된 경우에는 인덱스의 시작부터 정순으로 데이터를 가져오며, 이를 오름차순 스캔 방향이라고 합니다. 그러므로 MySQL에서 내림차순으로 정렬된 데이터를 가져올 때는 뒤에서부터 데이터를 스캔하여 값을 찾아오고, 오름차순으로 정렬된 데이터를 가져올 때는 앞에서부터 정순으로 데이터를 스캔하여 값을 찾아옵니다.

 

 

그러면 오름차순 스캔과 내림차순 스캔을 사용하는 것이 좋을까?

그것은 오름차순 스캔을 사용하는 것이 내림차순에 비해 성능적으로 좋다고 할 수 있다. 왜냐면 페이지 잠금이 인덱스 정순 스캔에 적합한 구조를 가지며 페이지 내에서는 단향향으로만 연결되어 있어 내림차순으로 스캔을 하게 되면 연결하는 만큼 성능이 감소하기 때문이다.

 

---

 

 

정리

B-Tree 인덱스는 데이터베이스 시스템에서 매우 중요한 역할을 한다. B-Tree 인덱스는 데이터의 빠른 검색과 효율적인 관리를 가능하게 하여 데이터베이스의 성능을 향상하고 확장성을 제공할 수 있습니다. 따라서 데이터베이스를 설계하고 구현할 때, B-Tree 인덱스의 활용을 고려하는 것이 필수적으로 고려해 볼 수 있다.