반응형 자료구조/🧩자료구조2 DataBase Index에서 기본적으로 HashTable이 아닌 B-Tree를 쓰는 이유 의문의 시작 해시 테이블은 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간복잡도를 가지는 좋은 성능의 자료구조인데 DateBase에서 Index로 사용안하는지 갑자기 의문이 생겼다. 지금 생각해보면 조금만 고민하면 답을 찾을 수 있는데 왜 안보였는지... 서치를 해보니 나와 같은 의문점을 가진 사람들이 꽤 있어서 자료가 찾기 편했다. 바로 알아보자! 자료구조 비교 HashTable HashTable이란 Key와 Value로 데이터를 저장하는 자료구조 중 하나로써, 데이터의 삽입, 삭제, 탐색에 평균적으로 O(1)이라는 빠른 성능의 시간복잡도를 자랑하는 자료구조이다. HashTable의 프로세스를 알아보면, 검색하고자 하는 키값을 입력받아서 해시함수를 통해 반환받은 HashCode를 배열의 Index로 .. 2023. 1. 9. Big-O 표기법과 처리속도에 관하여 Big-O는 알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 이것으로 알고리즘의 시간과 공간 복잡도를 표현할 수 있다. 시간과 공간 복잡도의 표현을 통해 정확한 알고리즘 시간을 산출하기보다, 데이터나 요청의 증가율에 따른 성능을 예측하는 것을 목표로 한다. Big-O 표기법을 알바오자. 먼저, 첫번째로 O(1)알고리즘이 있다. 이 알고리즘은 입력데이터의 크기와 상관없이 일정한 시간이 걸리는 알고리즘을 말한다. 위의 예와 같이 어떠한 데이터가 들어와도 동일한 시간이 걸리는 것을 보증한다. 이러한 경우를 O(1) 시간복잡도를 가진다고 표현한다. 그래프로 표현하면 아래와 같다. 두번째로, O(n)알고리즘이 있다. O(n)알고리즘은 입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘을 표현한다. 위의 .. 2021. 8. 16. 이전 1 다음 반응형
