2019.07.13 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

자료구조

1. 자료구조는 데이터베이스에 어떻게 데이터를 담을 것인지에 대한 이론이다.
2. 서버 개발자로서 굉장히 중요한 부분이다.

1. 전체적인 흐름

1. 동적배열(Dynamic array) vs 연결리스트(linked list)
   1. insert, delete, search에 따라서 효율이 다름
2. BST(array list와 linked list의 단점 보완)
   1. insert, delete, search 모두 O(log(n))
   2. 트리의 깊이가 깊어지면 문제 발생
3. 레드블랙트리(red black tree)
   1. self-balancing 기능이 생기면서 BST문제 해결
4. B-Tree
   1. 캐시기능 추가 보완
5. B+Tree

동적배열 vs 연결리스트

1. 동적배열(파이썬에서는 list가 동적배열이다 - 따라서 append와 pop은 O(1) )
   1. 장점 : search - (O(1) : 인덱싱때문에)
   2. 단점 : Insert, delete : O(n) - 최악의 경우는 제일 앞에 것을 지우고, 삭제할 때이다. 하나씩 다 옴겨줘야 한다.
   3. 할당되어 있는 전체 크기가 capacity라고 하는데, 만약 특정 위치에 값을 넣거나 삭제하려고 하면 자리를 계속 옴겨야 한다.
   4. 만약에 capacity가 꽉 찼는데 append해야 한다면 amortized analysis (분할 상환 분석-뒤에서 참고)
   5. 예) 파이썬의 list
2. 연결리스트
   1. 장점 : insert, delete : O(1)
   2. 단점 : search : O(n)
   3. 예) 더미 더블링크드 리스트
3. 만약에 쓴다고 하면 동적배열을 써야 한다. 정말 배열이 붙어있어서 지역성으로 캐시가 발생할 확률이 높다. 하드웨어의 이점을 받을 수 있다.
4. 이거 2개를 보완해주는게 BST이다.

BST(이진탐색트리)

• 이진탐색트리
• 루트를 기준으로 왼쪽에는 항상 더 작은 자료가 위치하고 오른쪽에는 더 큰 자료가 위치한다.
• *insert, delete, search 모두 O(log(n))
• 아무리 많이 해도 트리의 높이(height of tree)만큼만 하면 된다.log(n)
• 트리에 있는 것은 파이썬에서 key값이라고 볼 수 있다.
  • dictionary이고 a collection of pairs(key, item)
  • 해당 key에 item을 참조하게만 해놓으면 문제해결

BST를 공부하기 위해서 기본적으로 Tree에 대해서 알아야 한다. Tree의 search, delete, insert에 대해서 공부해야 한다.

redblack tree

참고 : RedBlack Tree에 대해

• 7,6,5,4,3,2,1 순서대로 삽입해서 이진탐색 트리(Binary Search Tree)를 만들어 보면 위의 그림과 같이 한쪽으로 치우처진 tree가 완성된다.

1을 찾으려고 한다면?

• 항상 트리의 높이만큼 시간이 필요하다. 그렇다면 이진탐색 트리(Binary Search Tree)를 사용하는 이유가 없다.
• 이러한 문제점을 해결하기 위해 나온 자료구조가 Balanced binary search tree의 한 종류인 RedBlack Tree이다.

• 각 노드에 색깔을 저장하는 공간을 추가하여 색깔을 기준으로 균형을 맞추는 트리이다.

자세한 사항은 또 뒤에서 redblack tree만 다루어보자.

B TREE

• 기존에 tree에서 할 수 없었던 캐시를(지역성) 추가하여 보완

• 한 개의 노드에 여러개의 데이터가 들어갈 수 있다.
• 지역성 문제를 해결하여 훨씬 효율을 높였다.

자세한 사항은 B tree만 다룬다.

추가

분할 상환 분석(Amortized analysis)

• 등장배경: 우리가 짜는 함수의 경우는 빅오를 구하기에 굉장히 애매한 경우가 많다. 따라서 대략적으로 빅오를 구하는 방법
• DA(동적배열)에서 append를 할때 메모리(capacity)가 꽉 찬 경우
• 메모리(heap)을 돌아다니면서 가능한 공간을 찾아다닌다. 가능한 위치를 찾아서 복사해서 넣게 되면 최소한 O(n)
• heap이 linked list로 구성되어 있다.
• 해결방안
  • 우리가 아는 데이터의 갯수가 200개이면 키자마자 250개를 잡아 놓는다.
    • 만약에 3개만 쓰게 되면 굉장히 비효율적이다.
  • 한 개씩 늘리면서 모든 공간이 다 차게 되면 크기를 X2 한다.
• 가끔 한번씩 O(n)이 필요한데 그만큼 하고 나몬 지속적으로 O(1)이 되므로 이정도는 그렇게 치자.
• ex) 데이터의 갯수가 3개이면 4개면 된다.
• 이렇게 하면 캐시히트와 인덱싱을 유지할 수 있다.
• heap안에 찾아다니면서 2배 크기가 가능한 곳을 찾아다니는 것이다.