B+ Tree, Hash Function

[dahyunko]

Question

• B+ tree
• Hash function

Answer

• B+ Tree : Bulk Loading

  • random vs sort 된 데이터 insert 성능 차이 있음

    → query optimizer가 최적화 작업을 해놔서 성능 차이를 알 수 없음

    • Sort 된 데이터는 cach hit ratio 올라감

    • random 된 데이터는 캐시를 사용할 수 없음

      

• 인덱스를 많이 잡는게 좋은 게 아님

  

• Hash Function

  1. Linear Probe hashing

     (key, value) : Tombstone → Movement 빈 칸 생기면 찾을 수가 없음

     문제 : 충돌이 많이 일어남, 같은 키값 다른 value

  2. Robin Hood Hashing : 부의 재분배

     • 충돌 횟수를 공평하게 분리한다, 충돌 횟수를 줄임

       

  3. Cuckoo Hashing (현업 cache indexing)

     

• Ghost marking

  • Structed Modification OverHead : 메모리 주소가 바꿔서 비용이 많이 들음, 개발자 실수, 데이터가 날아갈 수 도 있음 ⇒ 실제로 삭제하지 않음

    

  • 단점: 메모리적으로 공간을 낭비 할 수 있음

Explain about unknown concept