7. 데이터 구조와 처리

단일 연결리스트

• 배열은 물건 목록을 유지하는 가장 효율적인 방법이지만 데이터 양이 정해져 있지 않은 경우에는 적합하지 않음. 배열 크기보다 더 크게 데이터가 들어오면 새로 더큰 배열을 만들고 복사해야하기 때문.

• linked list 는 목록에 들어갈 원소 개수를 모르는 경우 배열보다 더 잘 작동함

동적 메모리 할당

• 배열 등의 변수가 사용하는 메모리는 정적. 이미 사이즈가 정해져있으므로. 주소도 바뀌지 않음

• 프로그램은 힙을 관리할 수 있어야 함. 프로그램은 사용중인 메모리를 알아야 하고, 사용 가능한 메모리도 알아야 함

• C에는 malloc 과 free 함수가 있음

• malloc을 사용해서 메모리를 할당을 하면서 시간이 지나면, 메모리 공간이 파편화되게 됨 → 메모리공간을 다 사용하지도 않았는데 너무 작은 가용 블록들만 남아서 malloc으로 요청받은 메모리를 돌려줄 수 없게 됐다는 뜻

가비지 컬렉션

• 가비지 컬렉션을 사용하는 언어는 데이터 요소를 만들어내면서 이 요소가 사용할 메모리도 할당하는 new 연산자를 제공하는 경우가 자주 있음

• 데이터 요소 삭제하는 경우는 언어의 런타임 환경이 변수 사용을 추적해서 더 이상 사용하지 않는 메모리는 자동으로 해제함

이중 연결 리스트

• 노드에 다음 원소에 대한 포인터뿐만 아니라 이전 원소에 대한 포인터도 들어있는 리스트

계층적인 데이터 구조

• 많은 애플리케이션의 경우 선형적인 데이터구조로 충분하지만 데이터를 효율적으로 가져오고 싶을 때에 그렇지 않음 ← 그 이유는 모든 데이터를 다 순회해야 하기때문

• 2진 트리. 연결리스트에서는 길이가 n이면 n번만 비교하면 되지만 균형 잡힌 트리에서는 log_2(n)만큼만 비교하면 됨

데이터베이스

인덱스

• 정렬된 데이터에 접근하면 더 효율적임

• 인덱스의 경우 유지보수를 해야한다는 트레이드 오프가 있지만 (데이터가 바뀔 때마다 모든 인덱스를 갱신해야하기에) 데이터 변경보다는 데이터 검색이 더 자주 벌어지기 때문에 이런 갱신비용은 지불할 만함

해시

정렬

효율성과 성능

샤딩

• 성능과 효율이 분리된 상황을 응용하는 방법으로 데이터베이스 샤딩(=수평 파티셔닝)

• 데이터베이스를 각각 다른 기계에서 실행되는 여러 샤드로 나누는 방식을 말함

• 인터페이스를 통해 요청이 들어온 데이터베이스 연산을 모든 샤드에 전달, 컨트롤러가 결과를 하나로 모음