heap vs sorted

[dahyunko]

Question

• heap vs sorted 탐색 비교
• 이진 탐색 트리 (BST)
• b tree
• b+ tree

Answer

• heap vs sorted 탐색 비교

  • scan all 은 둘다 걸리는 시간 똑같음
  • 범위 검색, 검색 sorted가 빠름
  • 삽입은 heap (append) 이 더 빠르다. sorted는 insert 여서 오래 걸림
  • 삭제는 비교 불가, 상황에 따라 다름
    • 정렬이 안 되어 있어서 heap은 비트맵을 활용해서 빠진 부분은 바로 넣을 수 있다.
    • sorted는 정렬을 해야 하므로 다음 insert가 발생할 때, 다시 순차적으로 찾아서 넣어주어야 함

• 이진 탐색 트리 (BST)

  • 문제점 : 트리가 한쪽으로 치우쳐지는 것이 문제
  • 위 문제점 해결 방안 : AVL 트리

    • 2이상 depth 가 차이가 나면 트리를 회전 시켜서 위 문제를 해결

    • 균형을 맞춰줌

    • 문제점 : 회전을 많이 시켜줘야함

      → depth가 깊어질 수록 disk I/O가 많이 발생함 ⇒ 시간이 오래 걸림

• b tree

  • heap + empty space : 데이터가 들어오는 것을 염두해서 공간을 비워주자
  • 빈칸이 없어지면?
    ⇒ 빈칸을 만들어줘야함 LinkedList 개념 추가
    • 순서대로 정렬이 안됨, log(n) 다 봐야함
    • 2.9는 overflow paged

• b+tree (ISAM)

  • 데이터가 삽입이나 삭제가 되어도 sorted를 유지할 수 있다.

• 인덱스

  • hash vs b+tree
    • hash는 범위 탐색이 안 좋음 → 모든 disk I/O 발생함
      단일 탐색에 좋음 → 포인터를 사용하기 때문
    • b+tree는 단일 탐색이 안 좋고 → disk I/O가 많이 발생함
      , 범위 탐색에 좋음 → 탐색하는 부분만 disk I/O발생함

Explain about unknown concept