B-Tree 인덱스, 해시 인덱스

B-Tree(Balanced Tree) 인덱스

트리의 노드가 한 쪽으로 치우치지 않게 하기 위해 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어 왼쪽과 오른쪽 자식 수의 밸런스를 유지하는 트리

• 양 쪽 자식 수의 밸런스를 유지하므로 O(logN)의 시간 복잡도를 가지게 된다.
• 노드 삽입 및 삭제 시 재정렬하는 작업때문에 탐색을 제외한 작업에서는 Tree보다 성능이 좋지 않다.
• 빠르게 데이터를 검색하는데 용이

B-Tree와 B+Tree 차이

해시 인덱스

해시 함수를 사용하여 데이터를 해시 값으로 변환하고 이를 인덱스로 사용하는 방법
B-Tree만큼 범용적이지 않지만 고유의 특성과 용도를 지닌 인덱스 가운데 하나이다.

• 일반적인 DBMS에서 메모리 기반의 테이블에 주로 구현되며 디스크 대용량 테이블 용으로 거의 사용되지 않는다.
• 동등 비교 조건을 갖는 검색에 유리

장점

• 실제 키 값과 상관없이 인덱스 크기가 작고 검색이 빠르다.
  • 검색하고자 하는 값을 주면 해시 함수를 거쳐 찾고자하느 키 값이 포함된 버켓(인덱스 키 값과 레코드 주소 값 등의 정보를 두는 공간)을 찾아냄
  • 버켓을 읽어 실제 레코드가 저장된 위치를 찾아내는 방법
• 원래 키 값의 길이가 저장되는 것이 아니라 함수 결과에 대한 값을 저장하기 때문에 컬럼의 길이가 아무리 길어도 저장되는 값은 현저히 줄어든다.

단점

• 함수의 결과 값의 범위가 너무 넓어지면 그만큼 많은 버켓도 필요하기 때문에 공간 낭비가 심해진다.

참고
https://enterone.tistory.com/227
https://velog.io/@sem/DB-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-B-Tree