B+Tree 2

[MySQL] 인덱스 자료구조

인덱스의 핵심은 탐색 범위를 최소화 하는 것이다. 그렇다면 탐색이 빠른 자료구조들은 어떤 것이 있을까? Hash Map, List, Binary Search Tree 등이 있는데, 하나씩 간단하게 살펴보도록 하자. ✅ HashMap - 단건 검색 속도 O(1) - 범위 탐색 O(N) - 전방 일치 탐색 불가 Ex) like 'AB%' 해시맵은 키와 밸류가 있다. 그렇기 때문에 단건 검색 속도는 빠른편이며 상수 시간이 걸리게 된다. 범위 탐색에는 O(N) 시간이 걸리게 된다. ✅ List - 정렬되지 않은 리스트의 탐색은 O(N) - 정렬된 리스트의 탐색은 O(logN) - 정렬되지 않은 리스트의 정렬 시간 복잡도는 O(N) ~O(N * logN) - 삽입 / 삭제 비용이 매우 높음 정렬되지 않은 리스트는..

Database/MySQL 2023.03.06

[DB] 데이터베이스 인덱스(Index)란 무엇인가?

아직까지 미미한 양의 DB를 다뤄보았기 때문에 데이터 양이 증가할수록 실행 속도가 눈에 띄게 느려지는 경험을 해보지는 못했다. 하지만 DB데이터의 양이 증가할수록 쿼리를 잘 사용해야하고, 쿼리의 성능을 높이는 데 중요한 것은 인덱스를 적재적소로 활용해야 함은 잘 알고 있다. 오늘은 인덱스의 개념과 구조, 그리고 필요성, 사용했을 때 장단점들에 대해 정리해보고자 한다. ✅ 인덱스(Index)란? 인덱스(Index)는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료구조이다. 테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장한다. 인..

Computer Science 2023.01.30
728x90