- 대용량 데이터는 HDD등에 저장됨
- Seek time : 헤드를 원하는 데이터가 섹터로 이동하는데 걸리는 시간
- 운이 좋으면 현재 헤드 밑에 원하는 섹터
- 운이 나쁘면 현재 헤드 바로 앞에 원하는 섹터
- rpm : 분당 회전 속도:7200rpm ~=0.01sec
- 데이터는 블럭 단위로 저장
- 한번 데이터에 접근 하는 시간이 많이 걸리고, 어차피 블럭 단위로 저장된다면 트리의 노드에 많은 정보를 넣고, 트리의 높이를 줄이는 것이 좋다.
- B-Tree : 균형잡힌 다진 검색 트리
- 한 노드에 하나 이상의 키 값이 들어올 수 있다.
- t개의 키 값이 저장되어 있다면, 이 노드의 자식은 t+1개이다.
- 루트를 제외한 모든 노드는 k/2~k개의 키를 갖는다.
- 모든 리프노드는 루트에서부터 거리가 같다.
- B-Tree 삽입
- 한 노드에 둘 이상의 키가 저장될 수 있기 때문에 복잡하게 진행된다.
- 키가 저장될 노드를 찾으면
- 이 노드가 키를 저장할 수 있다면 여기에 저장
- 이미 k개의 키를 저장하고 있어 불가능하다면, 이 노드의 형제 노드에게 키를 넘길 수 있는지 확인
- 만약 그렇지 않다면, 중간값을 기준으로 키들을 두 그룹으로 나누고 중간값은 부모에게 전달함
- 부모에게도 재귀적으로 진행
- 루트 부터 다음 과정을 반복
- 찾고자 하는 키가 현재 노드에 포함되어 있는가?- 만약 포함되어 있지 않다면, 범위를 보고 다음에 방문할 노드를 결정
- 한 노드가 최대 k 키를 저장하기 때문에 여러 값과 비교
- B-Tree 삭제
- 지워질 키가 속한 노드가 리프 노드가 아니라면
- 이 키의 바로 다음 값이 저장된 리프 노드를 찾고, 값을 서로 바꾼다. - 리프 노드에서 키 값을 제거한다.
- 만약 이 노드에 k/2개의 미만의 키가 남는다면
- 형제 노드 중 키 값을 넘겨줄 수 있는 노드를 찾는다.
- 만약 그렇지 않다면, 형제 노드와 이 노드를 합병한다.
- 노드를 합병하면 부모 노드의 키가 줄기 때문에 이 과정이 반복된다.
- 삭제했을 때 그 값보다 가장 근접한 값을 올린다.
- 지워질 키가 속한 노드가 리프 노드가 아니라면
- Reb-Black Tree 와 B-Tree의 관계
- 2-3-4 Tree : 한노드에 최대 4개의 자식이 올 수 있는 B-Tree
- Red 블랙 트리는 2-3-4Tree를 이진트리로 표현한 것이다.
백엔드 & 전공 공부