이전 쿼리 성능 개선에 대한 포스팅이 있었다.
https://velog.io/@wnsrb933/%EC%BF%BC%EB%A6%AC%EC%84%B1%EB%8A%A5%EA%B0%9C%EC%84%A0%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%98%EB%8A%94%EA%B0%80%EA%B8%B0%EC%B4%88
크흠.. 물론 엉망이지만.. 다음 게시글은 써야하니까..
원래 DB에서 검색을 할 때 어떻게 적용할까?
예시로 검색을 하나 해보자
select * from person where type = "family";위 처럼 하면 person table에서 type이 family인 사람을 검색한다
그럼 위 처럼 검색하면 DB가 1부터 찾다가 저 정보를 찾으면 바로 반환할까?
답은 아니다.
DB는 일단 index가 없을 경우 full-scan을 하고 반환한다.
데이터가 100개라면 100개를 다 뒤지고 해당 data를 반환하니 fullscan +1 이 최소 반환 연산이란 말이지..
보고 살짝 얼척이 없긴 했다. 컴퓨터 똑똑하다며?
근데 막상 생각해보면 DB는 어떤 구조일까? 생각이 든다
ArrayList 형태일지 LinkedList 형태일지 그렇게 한줄로 되어 있다면 그럴 수 있다 생각이 든다.
그럼 index가 있다면?
index를 사용한다면 일단 정렬이 되어있다.
CREATE INDEX idx_column_name ON table_name (column_name);인덱스는 creat index로 지정하여 할 수 있다.
물론 해당 컬럼 이름을 지정하고 on 뒤에 테이블과 컬럼의 이름을 지정해야한다.
SELECT * FROM table_name WHERE column_name = 'some_value';이렇게 하면 어떻게 될까? 이미 정렬되어 있는 index가 column_name으로 들어가있으니 풀스캔을 하지 않아도 되지 않는가?
그렇게 될 경우 검색 시간을 효율적으로 감소시킬 수 있다.
그럼 index는 어떻게 작용하냐?
방법은 binary-search-tree, b-tree, b+tree가 있다.
코딩애플 보고 띠용 했다.
모두 tree 구조이다.
각 특징에 대해서는 지선생님이 도와줬다.
Binary Search Tree (이진 검색 트리)
개념:
각 노드가 최대 2개의 자식 노드를 갖는 트리 구조.
왼쪽 서브트리는 현재 노드보다 작은 값, 오른쪽 서브트리는 큰 값을 가진다는 규칙을 지님.
중위 순회(In-order Traversal)를 하면 정렬된 순서의 값을 얻을 수 있음.
특징:
평균적으로 검색, 삽입, 삭제 연산 모두 O(log n)의 시간 복잡도를 기대할 수 있음.
하지만 데이터가 정렬된 순서대로 삽입될 경우 한쪽으로 치우친 형태가 되어(스큐드 트리, skewed tree) O(n) 성능 저하 발생.
장점과 단점:
빠른 검색 가능(평균적인 경우)
자료가 편향되면 성능이 급격히 나빠짐.
B-Tree
개념:
DB나 파일 시스템에서 널리 사용되는 트리 구조.
Binary Search Tree와 달리 한 노드가 다수의 키(key)와 자식 노드를 가질 수 있는 균형 트리(Balanced Tree).
루트와 리프를 제외한 내부 노드들이 최소 키 수와 최대 키 수를 갖는 규칙이 있고, 이러한 규칙으로 항상 트리 높이를 낮게 유지.
특징:
한 노드 내에 여러 키를 저장, 디스크 I/O 최적화에 유리.
노드 크기가 디스크 블록 크기와 유사하게 맞춰져, 한 번의 디스크 읽기(블록 I/O)로 여러 키 탐색 가능.
검색, 삽입, 삭제 모두 O(log n) 보장.
대부분의 DB 인덱스 구조에서 B-Tree 또는 변형 구조 사용.
B-Tree 연산:
검색: 루트부터 시작, 노드의 키 목록을 이진 검색 후 필요한 자식 포인터 따라 이동.
삽입, 삭제 시 노드 분할(Split) 또는 병합(Merge) 발생 가능하지만, 트리 높이가 크게 변하지 않음.
B+Tree
개념:
B-Tree의 확장형으로, 데이터베이스 인덱싱에 매우 널리 사용.
B-Tree와 유사하지만 모든 실제 데이터(레코드에 대한 포인터)는 리프 노드에만 저장.
내부 노드는 서브트리의 범위를 나타내는 키만 저장.
리프 노드끼리 연결되어(Linked List 형태) 순차적 접근(범위 검색) 효율이 좋음.
특징:
리프 노드가 데이터에 대한 실제 포인터를 갖고 있으며, 리프 노드 모두가 Linked List로 연결.
순차적 스캔에 매우 유리, 범위 질의(Range Query)에 강점.
DB 인덱스 구조로 가장 널리 쓰임.
장점:
범위 검색 시 리프 레벨에서 순차 접근이 가능하여 빠른 Range Scan.
B-Tree 대비 디스크 접근을 최소화하고, 더 균일한 성능 제공.
더 자세한 내용에 대해서는 생략하고 일단 어떤 구조인가에 대해 대략 설명을 한다면
binary-search-tree의 경우 이진탐색이다. 효율적이긴 하나 더 많은 데이터를 빠르게 스캔하기 위해 잘 사용하지는 않는다.
게다가 균형이 보장되지 않으면 성능이 저하된다는 이슈가 있다.
그래서 b-tree와 b+tree를 사용하는데 이는 트리 구조에 자식 노드를 상요하여 균형 트리를 만들고 규칙을 지정하여 최적화를 할 수 있게 한다.
이진 검색 후 자식 포인터를 따라 이동한다.
b+tree는 실제 데이터에 대한 포인터는 리프 노드에만 저장하고 내부 노드는 서브트리의 범위를 나타내는 기만 저장하여 범위 검색에 효율이 좋다.
하지만 단점은 전에 말한 것 처럼 분명하다.
단점
인덱스 생성 및 유지 보수 비용 발생(삽입, 삭제, 업데이트 시 인덱스도 함께 수정 필요).
너무 많은 인덱스는 오히려 DML(Insert/Update/Delete) 성능 저하.
논점
그래서 나는 조회만 필요한 기능에 대해 따로 분리를 해도 되지 않을까 생각한다..
그래서 DB를 두개 써볼까?, 혹은 아예 조회테이블을 따로 만들까? 생각을 했다.
그렇긴 한데 이러면 쿼리가 복잡해지거나 동기화가 어려워 참조 일관성을 유지하기 어렵다는 결론이 도출됐다..
이걸 배포를 어떻게 하나 계속 생각해보고 응용계층에서 두 DB에 대한 커넥션, 모니터링 부담이 힘들어지고 난이도가 급상승하더라..
혹시 DB 싱크가 안맞으면 일관성이 없어지는건데 그럼 ACID는 고물상 아저씨한테 넘기는 꼴이 되지않는가..
실제로 찾아보니 data warehouse, data lake로 분리하여 사용하는 전략과 검색엔진은 대용량 정적 데이터를 별도 검색 서버(redis, elk)에 두고 빠른 조회를 하게 한다더라..
이것도 좋은 방법같은데 한번 공부를 해봐야겠다.
참고 :
https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC
https://inpa.tistory.com/entry/MYSQL-%F0%9F%93%9A-%EC%9D%B8%EB%8D%B1%EC%8A%A4index-%ED%95%B5%EC%8B%AC-%EC%84%A4%EA%B3%84-%EC%82%AC%EC%9A%A9-%EB%AC%B8%EB%B2%95-%F0%9F%92%AF-%EC%B4%9D%EC%A0%95%EB%A6%AC
