1일1개 (6) - Index (B+ Tree, Hash Table)

1일 1개념정리 24.08.09.금 ~ 

 

큰 결정에 큰 동기가 따르지 않을 때도 있다. 하지만 큰 결심이 따라야 이뤄낼 수 있다.

무조건 무조건 1일 1개의 개념 정리하기 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!

---

#6. 인덱스란 ?

인덱스가 무엇인가 ?? 우리가 책의 목차를 보고 몇페이지부터 읽어야지~ 하거나, 책의 맨 뒤에 단어들이 몇페이지에 나왔는지 알려주는 페이지를 보고 해당 페이지로 간다거나 이런 것들이 모두 인덱스를 이용한 것이다. 보통 "색인(索引; 찾을 색 , 끌 인)"이라고도 하는데, "책 속의 단어나 구절을 찾아보기 쉽도록 나열한 목록"을 말한다. 이를 우리는 인덱스라고 부른다. 우리가 말하는 인덱스는 보통 데이터베이스에서 나온다. 무언가를 찾을 때 인덱싱한다고 말하기도 한다.

 

인덱스 장단점

인덱스를 쓰면 Select 시간을 효과적으로 단축해서 무조건 이득일 것 같지만, 모든 것엔 Trade-off가 있다.

장점

• 테이블 조회 시간 단축 : 인덱스는 특정 열에 대한 정렬된 구조를 유지하므로, 데이터를 빠르게 검색할 수 있다. 이는 특히 SELECT 쿼리에서 조회 성능을 극적으로 향상시킨다.
• 복잡한 쿼리 최적화 : 인덱스는 복잡한 쿼리, 특히 Join, 집합, Where절의 최적화에 중요한 역할을 한다.

단점

• 추가적인 저장공간 필요 : 인덱스를 생성하면 DB는 해당 인덱스를 저장하기 위해 추가적인 저장공간을 할당해야 한다. 그래서 인덱스가 많아지면 데이터보다 오히려 인덱스가 차지하는 공간이 더 커질 수도 있어서, 대규모 DB에서는 이에 따른 저장 비용을 증가시킬 수 있다.
• 인덱스 관리의 복잡성(= 추가 관리 필요) : 데이터가 변경될 때마다 관련된 인덱스도 함께 갱신되어야 하므로, 인덱스가 많을수록 데이터 수정 작업(insert, update, delete)이 느려질 수 있다. 이는 데이터 변경이 빈번한 테이블에서는 성능 저하로 이어질 수도 있다.

인덱스는 검색 속도를 크게 향상시키지만, 그만큼 저장공간을 추가로 소비하는 트레이드 오프가 있다. 따라서 무조건 인덱스를 무슨 신처럼 많이 만들 것이 아니라, DB 사용 패턴에 따라 필요한 인덱스를 신중하게 설계하는 것이 중요하다.

 

인덱스 자료구조

인덱스를 구현하기 위해 보통 나오는 자료구조가 B+Tree와 Hash Table이다. 

 

1. B+ Tree

약간은 생소한 자료구조일 수 있다. B-Tree를 발전시킨 것이 바로 B+ Tree인데, 아래와 같이 생겼다. 트리의 특징을 알아보자.

 

• B+ Tree는 모든 key값이 정렬되어있다. 정렬하는 이유는 보통 다음과 같다.
  • 1) 효율적인 탐색 가능 : 이진탐색 쓰기 위해 정렬한다.
  • 2) 삽입, 삭제가 용이함 : 정렬되어있어서 적절한 위치를 찾기가 쉽다.
• Sibliling 노드가 연결 리스트로 이어져있다. 이를 통해 순차 검색을 용이하게 한다. 여기서 말하는 "순차 검색"이 쉽다는 의미는, 만약 내가 특정 범위의 데이터를 연속적으로 읽어야 하는 경우, 첫 번째 키를 찾은 후 리프 노드들을 순차적으로 따라가면 나머지 키들을 쉽게 추출할 수 있다는 것이다.

 

2. 해시 테이블

해시 테이블은 특정 키를 빠르게 검색하거나 저장하는 데 유용하다. 해시 테이블로 만든 인덱스는 Key, Value 쌍을 통해 데이터의 위치를 기록하여 빠른 조회를 가능하게 한다. 그러나 B+ Tree보다는 제한적이라 인덱스 구현에 잘 사용되진 않는다고 한다. 그 이유는 아래에서 살펴보자 !!

해시테이블의 특징은 다음과 같다.

• Key, Value 쌍 : 해시 테이블은 입력값을 해시 함수로 고유한 인덱스를 생성하고, 이 인덱스에 값을 저장하는 방식으로 작동한다. 이렇게 저장된 값을 다시 검색할 때도 동일한 해시 함수를 사용하여 키에 대한 인덱스를 계산하고, 해당 위치에 저장된 값을 빠르게 가져올 수 있다.
• 시간복잡도 O(1) : 해시 테이블의 가장 큰 장점은 검색 시간이 O(1)이라는 것이다. 해시 함수가 키에 대해 고유한 인덱스를 생성하기 때문이고, 직접 해당 위치로 접근할 수 있어서 매우 빠른 속도를 가진다.

그러나 해시테이블은 보통 인덱스로 잘 사용되지 않는다. 바로 다음과 같은 단점 때문이다.

 

해시 테이블 기반 Index 구현의 한계

1. 부등호 연산(범위 검색) 비효율적 : 해시 함수는 input이 조금만 달라져도 완전 다른 값을 생성하기 때문에 "등호 연산"은 효과적이지만 그 외 부등호 연산(>, <)에는 부적합하다. 그래서 "100보다 큰 값"처럼 범위 검색은 해시 테이블에서 비효율적이다. 해시값이 키의 순서나, 크기와 직접적인 관계가 없기 때문이다. 따라서 해시 테이블을 사용하면 이러한 쿼리에서 인덱스의 성능을 전혀 활용할 수 없다.
2. 순차 접근/범위 쿼리 비효율적 : 해시 테이블은 데이터 저장시 정렬을 안해서 위에서 B+ Tree의 장점이었던 순차 접근이 여기서는 매우 비효율적인 작업이 된다. 비슷한 맥락으로, 범위 기반 쿼리도(Between, Like) 해시 테이블에서는 비효율적이다.

 

B+ Tree  VS  Hash Table

결론적으로, Hash Table은 앞선 여러 이유들로 인덱스에 그렇게까지 적합하지는 않다는 것을 알 수 있었다.

 

인덱스 구현시 B+ Tree가 적합한 이유 정리

• 범위 검색 효율성 : B+ Tree는 데이터가 정렬된 상태로 저장되고 리프 노드끼리 연결되어 있어서 범위 기반의 검색이 매우 효율적이다. 예를 들어, "나는"으로 시작하는 데이터를 찾을 때 B+ Tree는 빠르게 찾을 수 있다.
• 다양한 쿼리 최적화 : B+ Tree는 등호 연산뿐만 아니라, 부등호, BETWEEN, LIKE 등 다양한 쿼리 조건에 대해 효율적인 검색을 제공한다.

결론

해시 테이블은 매우 빠른 검색 성능을 제공하지만, 그 특성상 등호 연산에만 최적화되어 있으며, 범위 검색이나 순차적 접근이 필요한 데이터베이스 환경에서는 부적합하다고 볼 수 있다. 반면에, B+Tree는 다양한 쿼리 조건을 효율적으로 처리할 수 있어 인덱스에 더 적합하다.