색인(index)의 두 가지 형태 : LSM 트리 & B 트리 -2

0. 갑자기 궁금해서 찾아본 것 [ Optimistic Concurrency Control & Pessimistic Concurrency Control ] - Optimistic Concurrency Control 사용자들이 같은 데이터를 동시에 수정하지 않을 것을 가정한다. 읽는 시점에 Lock을 걸지 않는 대신 수정 시점에 값이 변경되었는지 검사한다. - Pessimistic Concurrency Control 사용자들이 같은 데이터를 동시에 수정할 것을 가정한다. 데이터를 읽는 시점에 Lock을 걸고 transaction 완료시점까지 유지한다. 1. BST - 정렬된 인메모리 자료구조이다. - 키-값 쌍 검색에 사용한다. - 키와 두개의 자식포인터가 저장된 여러 노드로 구성되며, 트리에는 단 한개의 루트노드만 있을 수 있다. - 탐색공간을 왼쪽 서브트리와 오른쪽 서브트리로 분할한다. - 루트에서부터 왼쪽 포인터를 따라 leaf 레벨까지 내려가면 트리에서 가장 작은 키, 반대로 오른쪽은 가장 큰 키이다. - 탐색은 루트에서 시작하고 대상 키를 찾으면 리프 레벨에 도달하기 전에 탐색이 끝날 수 있다. 2. 트리 밸런싱 - 노드 삽입 작업에는 특정 패턴이 없고, 삽입하는 값에 따라서 트리가 불균형 해 질 수 있다. - 최악의 상황에는 로그복잡도 트리가 아니라 선형 복잡도의 링크드리스트 형태가 될 수 있다. (skewed binary search tree(편향 이진 탐색 트리)) - 즉, 트리의 균형이 중요하다. 한 쪽으로 치우친 경우는 매우 비효율 적이기 때문이다. 3. 디스크 기반 스트리지용 트리 - BST 를 디스크에서 제어하면 발생하는 몇 가지 문제 1. 지역성 : 새로운 노드와 부모 노드가 가까운 위치에 저장되지 않을 수 있음. 2. 트리의 높이 : 자식포인터를 따라가는 비용과 밀접한 관계가 있음 1. 노드가 가질 수 있는 최대 자식 노드 개수 → fanout ** 결론은, 지역성을 고려하지 않는 자료구조는 비교횟수만큼 디스크 탐색이 필요할 수 있으니 지역성이 결여된 자료 구조는 피하자. - 인접한 키의 지역성을 높이기 위한 높은 fanout - 트리 순회 중 디스크 탐색 횟수를 줄이기 위한 낮은 트리높이 4. HDD - 디스크에서는 seek 작업이 랜덤 읽기 비용의 많은 부분을 차지한다. - 디스크를 회전하고 읽기/쓰기용 헤드를 원하는 위치까지 물리적으로 옮겨야 하기 때문이다. - 디스크의 최소 전송 단위는 sector 이다. - 모든 작업은 최소 한개의 sector를 읽거나 쓴다. - 물리적 헤드 이동은 HDD 작업 중 가장 비용이 높은 작업이다. 5. SSD - 물리적으로 움직이는 부품이 없다. - 회전하는 디스크도, 이동시킬 헤드도 없다. - cell로 구성된다. - cell → string → page → block - cell은 한개 또는 여러 개의 bit를 저장한다. - page가 읽고 쓸 수 있는 가장 작은 단위, 또한 비어있는 cell에만 쓸 수 있다. - 삭제할 수 있는 단위는 block → erase block - block 내 page는 순차적으로 쓴다. - 효율적인 디스크 기반 자료구조 설계가 어려운 이유는 - 디스크 접근비용 - block 단위로 삭제가 가능 6. 유비쿼터스 B-트리 - 도서관의 카탈로그 룸에서 원하는 도서를 찾는것과 유사하다. - 검색항목을 빠르게 찾을 수 있는 계층형 자료구조이다. - fanout이 높고 높이가 낮은 BST 기반의 트리이다. - B-트리는 키의 순서가 보장이 되고, 노드 키를 기준으로 정렬해서 저장하기 때문에 이진 탐색같은 알고리즘을 사용해 특정 키를 찾을 수 있다. 7. B-트리 계층 - 각 노드는 최대 N개의 키와 N+1개의 자식 노드 포인터를 저장한다. - 루트노드 : 트리의 최상위 노드로 부모 노드가 없음 - 내부노드 : 루트와 리프 노드를 연결하는 모든 노드 - 리프노드 : 자식노드가 없는 트리의 최하위 계층 노드 - B-트리는 page 기반 자료구조라서, 노드와 페이지가 같은 의미로 쓰이기도 한다. - B-트리는 리프노드에만 데이터가 있고, 나머지 노드는 데이터를 찾아가는 포인터를 가지고 있다. 8. B-트리 쓰기 - 쓰기는 여러 Disk write가 필요할 때가 있다. - 중간에 crash 하는 경우 데이터가 corrupted 될 수 있다. - 때문에 Write-ahead log(WAL) 이라는 파일에 어떤 write 를 할 지 미리 쓰고나서 작업을 이어간다. (LSM tree 에서의 log file과 유사) 1. B-트리 개요 - B-트리는 가장 많이 사용되는 자료구조 중 하나다. 근데, 이게 최신 알고리즘은 아니라고 한다. -