목록보조 인덱스 (1)

홍카나의 공부방

[데이터베이스] B+Tree, 인덱스의 종류

B+ 트리 MySQL은 B+트리로 인덱스가 구현되어 있다. B+ 트리는 인덱스 세트와 순차 세트라는 2가지 세트를 만든다. 인덱스 세트는 내부 노드로, 리프에 있는 키들에 대한 경로만 제공한다. 모든 키 값은 순차 세트(리프 노드)에 있다. 인덱스 세트는 직접 탐색을 지원하며, 순차 세트는 순차 탐색을 지원한다. B+ 트리는 B트리와 다르게 Best도 없고 Worst도 없다. 탐색은 무조건 O(log N)이다. B+ 트리의 루트 및 내부 노드 구조에는 레코드에 대한 포인터 값이 제외되어 있다. 반대로 리프 노드는 루트 및 내부 노드와 다르게 서브트리에 대한 포인터가 없다. 대신 레코드에 대한 포인터 값이 있고, 다음 리프노드에 대한 포인터가 존재한다. 순차 세트의 모든 리프 노드는 링크드 리스트 형태로 ..
Data Engineering/Database 2023. 5. 18. 16:54
이전 Prev 1 Next 다음