생각보다 기본기가 많이 부족했었나봅니다.
알고있는 내용의 대부분을 다시 공부해보니 새로 알게된 내용이 많았습니다.
그 중에 오늘은 DB 인덱싱이 무엇이고, 어떻게 동작하는지 같이 알아보겠습니다.
인덱스
인덱스(Index)란 데이터베이스에서 검색과 조회를 빠르게 하기 위한 데이터 구조입니다.
매우 큰 데이터량을 가지고 있는 데이터베이스일수록 특정 데이터를 찾는데 매우 오랜시간이 걸리는 데요.
인덱스는 특정 데이터를 효율적으로 찾을 수 있도록 돕는 기능입니다.
1. 인덱스 생성
적용하고 싶은 엔티티 테이블의 특정 컬럼에 대해 인덱스를 생성합니다. 이 열의 데이터로 정렬이 되는데요.
이때에 정렬되는 기준을 확인해보겠습니다.
ID NAME
3 Tom
1 Alice
2 Bob위 테이블을 기준으로 설명하겠습니다.
인덱스의 정렬은 키값이 문자열일 경우에는 알파벳 순서로, 숫자인 경우에는 숫자 순서로 정렬이 되게 됩니다.
요약하자면, 인덱스는 키값의 데이터 타입에 따라 적절한 방식으로 정렬이 됩니다.
JPA 기준으로는 인덱스 관련 코드를 작성하지 않아도 됩니다. 대신 인덱스 어노테이션을 확인하면 JPA가 자동으로 인덱스를 활용한 쿼리를 생성합니다.
@Entity
@Table(name = "user",
indexes = {
@Index(name = "idx_name", columnList="name", unique = true)
}
)
public class User {
@Id
@GeneratedValue
private Long id;
@Column(name = "name")
private String name;
// other fields, getters and setters
}
2. 인덱스 수정
해당 엔티티 테이블에 데이터가 추가, 수정, 삭제가 된다면 인덱스 또한 함께 업데이트 됩니다. 인덱스는 데이터 변경에 따라 추가 관리 비용이 발생합니다.
이때도 정렬기준에 따라 정렬이 자동으로 됩니다.
3. 인덱스 사용
쿼리 실행 시, 데이터베이스는 인덱스를 사용해 쿼리의 WHERE 절에 해당하는 데이터를 빠르게 찾을 수 있습니다.
인덱스가 없으면 전체 테이블을 스캔해야 하지만 인덱스가 있으면 특정 데이터를 훨씬 빠르게 찾을 수 있습니다.
코드 측면에서 보면 인덱스를 적용하기 전과 후의 구문 자체에서는 차이가 거의 없습니다. 그래서 인덱스가 적용된 컬럼을 where절에 사용해서 필터링 한다면 데이터 베이스가 알아서 인덱스가 적용된 필드로 필터링을 하게 됩니다.
SELECT * FROM user WHERE name='Sooho';
인덱스의 원리
인덱스는 어떤 알고리즘으로 만들어져있을까요? 일반적으로 인덱스는 해시테이 혹은 B+Tree알고리즘을 사용합니다. 데이터를 저장하고 검색하기 위한 아주 효율적인 알고리즘 입니다.
B-Tree
B-Tree는 각 노드가 여러개의 자식을 가질 수 있는 구조입니다.
노드 내의 키들은 정렬된 상태를 유지하고, 키 사이에는 포인터가 있어서 자식 노드를 가리킵니다.
보기에는 BST와 유사합니다.
하지만 B-Tree의 경우 자식 노드가 2개이상인 트리입니다.
각 노드 내의 데이터는 1개 이상일 수 있습니다.
노드의 데이터 수가 n개라면 자식 노드의 개수는 n+1개입니다. (초기 root의 경우나 leaf노드 제외)
근데 B-Tree는 왜 빠를까요?
B-Tree는 어떤 키를 찾더라도 같은 시간안에 찾을 수 있다는 것입니다. B-Tree를 균형잡힌 트리라고 많이 하는데요.
B-Tree는 노드를 삽입하거나 삭제할 때마다 트리의 균형을 유지합니다. 그렇기 때문에 모든 리프노드가 동일한 깊이를 가지게 되기 때문에 검색의 시간이 일정한 것입니다.
B-Tree에 값이 추가되는 과정은 다음과 같습니다.
- 차수에 따라 알고리즘이 다릅니다. (2*차수-1)
- 삽입되는 데이터는 항상 leaf노드에 추가됩니다.
- 추가될 leaf노드에 여유가 있다면 삽입합니다.
- 추가될 leaf노드에 여유가 없다면, 노드 데이터 중 (node/2)를 부모노드로 옮기고 좌우로 분할한 뒤에 삽입합니다.
B-Tree는 중위순회로 돌아갑니다.
B-Tree의 과정이 헷갈리시다면, 다음의 사이트에 들어가셔서 실제 생성과정을 한번 확인해보시는 것을 추천드립니다.
https://www.cs.usfca.edu/~galles/visualization/BTree.html
B-Tree Visualization
www.cs.usfca.edu
하지만 이런 B-Tree도 생성시기에는 균형을 갖춘 트리이지만 갱신이 계속 반복된다면 균형이 깨지게 되어 성능도 악화된다고 합니다.
따라서 어느정도 갱신 빈도가 높은 테이블에서 인덱스를 생성한다면 인덱스 재구성을 통해 트리의 균형을 회복하는 작업이 필요하다고 합니다.
B+Tree
B+Tree는 B-Tree의 확장 개념으로,
특정 키값이 한 노드에만 존재하는 것이 아닌 leaf노드와 부모노드에 공존하게 됩니다.
실제 데이터는 leaf 노드에만 존재합니다.
leaf 노드가 아닌 노드는 데이터의 빠른 접근을 위해 인덱스 역할만 수행합니다.
여기서 중요한 것은 leaf 노드들은 연결 리스트 형태로 서로 연결되며, 오름차순으로 정렬이 되어있습니다.
B+Tree에 값이 추가되는 과정은 다음과 같습니다.
- leaf노드와 부모노드에 키가 중복되어 존재하고, 연결리스트 형태로 leaf노드들이 모두 연결되어 있습니다.
- 차수에 따라 알고리즘이 다릅니다.
- 추가될 leaf 노드에 여유가 있다면 삽입합니다.
- 여유가 없다면 입력될 n으로 (n/2+1) 노드를 부모노드로 올리고 분할하여 연결리스트를 형성합니다.
B+Tree의 과정이 헷갈리시다면, 다음의 사이트에 들어가셔서 실제 생성과정을 한번 확인해보시는 것을 추천드립니다.
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
B+ Tree Visualization
www.cs.usfca.edu
해시 테이블
해시 테이블은 키를 해시 함수에 통과시켜 나온 결과값(해시값)에 따라 데이터를 저장하고 검색하는 구조입니다.
해시 테이블은 키-값 쌍을 저장하지만 키는 해싱 함수를 통해 생성됩니다.
그렇기 때문에, 인덱스 값이 데이터 값에 대한 키로 동작하므로 매우 빠른 데이터 액세스가 가능합니다.
따라서 키 값 자체가 데이터를 저장하는 배열의 인덱스가 되기 때문에 데이터 요소의 검색 및 삽입 기능이 훨씬 빨라집니다.
조회하는 동안 키가 해시되고 결과 해시는 해당 값이 저장된 위치를 나타냅니다.
해싱의 개념은 버킷 배열에 항목(키/값 쌍)을 배포하는 것입니다.
키가 주어지면 알고리즘은 항목을 찾을 수 있는 위치를 제안하는 인덱스를 계산합니다.
이 때문에 해시 테이블은 키에 대한 조회가 상수 시간, 즉 O(1)에 가능하다는 큰 장점이 있습니다.
하지만 해시 테이블은 레인지 쿼리를 지원하지 않습니다. 즉, "10에서 20 사이의 모든 값을 찾아라"와 같은 쿼리를 수행하는 것이 불가능합니다. 이는 해시 테이블이 키의 순서 정보를 유지하지 않기 때문입니다.
즉, 등호(=) 연산에만 특화되어있습니다. 부등호 연산(>, <)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블이 적합하지 않습니다.
또한, 해시 테이블은 '해시 충돌'이라는 문제를 가지고 있습니다. 다양한 키가 같은 해시값을 가질 때 충돌이 발생하며, 이를 해결하기 위한 다양한 방법들이 있지만, 이로 인해 해시 테이블의 성능이 저하될 수 있습니다.
따라서, 레인지 쿼리나 순서 정보가 필요한 경우에는 B+ Tree와 같은 자료구조를 사용하며, 특정 키에 대한 빠른 조회가 필요한 경우에는 해시 테이블을 사용합니다. 또한, 실제로는 B+ Tree와 해시 테이블을 함께 사용하는 경우도 많습니다. 일반적으로 B+ Tree는 레인지 쿼리를, 해시 테이블은 특정 키에 대한 빠른 조회를 지원하는 용도로 사용됩니다.
인덱스..
실제로 여러 자료구조로 구현되어 있었네요.
지금이라도 알게되어서 다행입니다.
여러 자료구조를 좀 더 공부 해봐야겠습니다.
댓글