[파일처리] Ch9 Multilevel Indexing and B-Trees
Binary Search Trees장점1) 데이터가 물리적으로 정렬되지 않는다2) 트리가 balanced 상태일 때 성능이 좋다3) 삽입비용과 검색비용이 같다 단점1) 트리가 unbalanced 상태일 때는 더 많은 탐색이 필요하다 예를 들어 아래와 같이 정렬된 key들이 있다고 가정하자AX, CL, DE, FB, FT, HN, JD, KF, NR, PA, RF, SD, TK, WS, YJ 그럼 balanced 이진 탐색 트리는 아래와 같을 것이다. 그러나, 이진 탐색 트리가 비대칭적으로 형성된다면 아래와 같이 탐색 효율은 급격히 감소하는 것을 볼 수 있다. Paged Binary Tree 이진 트리를 페이지로 나눈 다음 각 페이지를 디스크의 연속 위치 블록에 저장하는 이진 트리를 칭한다.위와 같은 p..
2024. 6. 5.
