b*tree 인덱스의 구조 및 성능 1

b*tree 인덱스(이하 인덱스)는 데이터베이스 성능 개선에서 가장 기본적으로 고려되어야 할 사항입니다.

기본적으로 PK는 인덱스가 생성이 됩니다. 이것은 PK를 대상으로 FK를 생성하였을 경우 FK의 값을 입력시 PK에 FK의 입력될 값이 있는지를 확인하여야 하는데, 이 확인하는 작업에 대해서 최대한의 성능을 고려한것이 PK에 인덱스를 생성하는 것입니다.

그럼 인덱스의 구조에 대해서 알아 보겠습니다.

인덱스는 기본적으로 밸런스의 구조를 가지고 있습니다.

밸런스의 최상위를 ROOT BLOCK 이라 하고, 최하위를 LEAF BLOCK 이라 하며, ROOT BLOCK과 LEAF BLOCK 사이를 BRANCH BLOCK 이라 합니다.

최초 1이라는 값을 입력을 하면 ROOT BLOCK에 1이 입력이 되고, 1이 입력된 LEAF BLOCK의 주소를 지정합니다.

이후 2를 입력하면 ROOT BLOCK에 입력된 1 이 2 로 바뀐뒤 LEAF BLOCK에 2가 추가되고 ROOT BLOCK 의 2에 1,2 가 저장된 LEAF BLOCK 주소가 그대로 지정됩니다.

만약 하나의 LEAF BLOCK에 100개의 값이 들어갈 수 있다고 가정을 하면(일반적으로 그 이상이 들어갑니다.) 1부터 100을 입력하면 ROOT BLOCK에는 100 이라는 값 하나가 있고, LEAF BLOCK에 1부터 100까지가 입력이 됩니다.

그후 101을 입력을 하면 ROOT BLOCK에는 100, 101의 값이 저장되게 되면 LEAF BLOCK은 2 개가 되어 하나에는 1부터 100이 다른 하나에는 101이 저장이 되겠죠.

이런식으로 ROOT BLOCK이 다 채워질려면 100, 200, 300 ......10000 이렇게 100개의 값이 저장되고 LEAF BLOCK는 100개가 저장이 될 것입니다.

이렇게 생성된 인덱스를 이용하여 데이터 조회시 204 의 값을 조회시 ROOT BLOCK에서 204는 200보다 크고 300보다는 작으므로 300이 가리키는 LEAF BLOCK에서 204를 찾게 됩니다.

그러면 단순 비교만 하더라도. 인덱스를 FULL SCAN 했을 경우 100개의 BLOCK를 조회해야 하는데, 인덱스 구조로 조회를 하면 2개의 BLOCK가 조회하면 되므로 조회시 성능에 월등한 향상을 가져올 수 있습니다.

물론 인덱스는 데이터 저장시 어느 정도의 추가적인 작업이 필요합니다.

하지만 이러한 추가적인 작업에 비해 조회시 너무나 월등한 성능을 보여주므로 데이터베이스  성능에 있어서 인덱스를 가장 기본적으로 고려해야 한다는 것입니다.

오늘은 b*tree 인덱스의 기본적인 구조에 대해서 알아보았습니다.

다음은 밸런스가 어떻게 깨지는지에 대해서 알아보겠습니다.