해당 내용은 

그림으로 공부하는 IT 인프라 구조를 기반으로 정리하였습니다.

 

1. 배열과 연결 리스트

 

배열과 연결리스트는 모두 순차적으로 데이터를 처리하는 구조이지만, 구조가 다르기에 성능 측면의 특징도 많이 다르다.

배열과 연결리스트는 다양한 데이터구조를 이해하기 위한 기본 구조이다.

 

배열은 같은형태의 상자를 빈틈없이 순서대로 나열한 데이터 구조다. "같은크기" 의 상자를 "빈틈없이 순서대로" 나열하기 때문에 몇 번째 상자인지만 알면 해당 상자에 한번에 액세스 할 수 있다.

 

 연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조다. 다음 상자의 위치 정보를 가지고 있다. 빈틈 없이 나열되지 않아도 되는 대신, 상자를 찾으려면 끝에서부터 순서대로 하나씩 상자 내부를 확인해야 한다.

 

즉 배열이 탐색은 빠르다. 하지만 배열은 도중에 상자를 추가하려면 그 이후 상자를 전부 하나씩 뒤로 옮겨야 한다. 상자를 빼는 경우엔 모두 하나씩 앞으로 옮겨야 한다. 이런 이유로 배열은 데이터 추가 및 삭제가 느린 데이터 구조라고 할 수 있다.

 

반면 연결 리스트는 도중에 상자를 추가하거나 삭제하면 선만 바꿔서 연결 해주면 된다. 따라서 연결 리스트는 데이터 추가, 삭제가 빠른 데이터 구조라 할 수 있다.

 

 특징을 간단히 정리하면 다음과 같다.

 

  •  배열은 데이터를 빈틈없이 순서대로 나열한 데이터 구조
  • 연결 리스트는 데이터를 선으로 연결한 데이터 구조
  • 탐색이 빠른 것은 배열이고, 느린 것은 연결 리스트
  • 데이터 추가, 삭제가 빠른 것은 연결 리스트, 느린 것은 배열.

 

참고로 위의 탐색은 처음부터 연속으로 찾는 것을 의미하는 것이 아니라, N 번째 요소 탐색을 의미한다. 

 

위의 삭제가 빠른 연결 리스트와 탐색이 빠른 배열을 조합한 하이브리드형 데이터 구조가"해시 테이블" 이다.

 

 2. 해시 테이블 / 트리, 인덱스

 

간단히 얘기하자면, modular 연산을 통해, 배열의 어느 인덱스에 해당하는 놈인지 찾고.

이 배열에는 각각 연결 리스트가 있어서, 배열에 연결된 연결 리스트 안의 데이터를 순차적으로 탐색해서 똑같은 놈이 있는지 찾아낸다.

 

해시 테이블은 키와 값 조합으로 표를 구성한 데이터 구성이다. 키는 해시 함수를 통해 해시 값으로 변환된다. 해시 값은 고정길이 데이터이기 때문에 조합 표의 데이터 구조가 간단해서 검색이 빠르다는 장점이 있다. 해시 테이블에서는 아무리 데이터 양이 많아진다고 해도 기본적인 등호 검색의 속도는 변하지 않는다. 

 검색 속도는 1이나 다름 없으나, 범위 검색이 약하다는 문제가 있다.

 

데이터베이스에서 인덱스를 사용하면 왜 검색이 빨라지는 걸까?

인덱스를 사용한다고 해서 항상 빨라지는 것이 아닌 이유는 왜일까?

기존 DBMS와 인메모리 DB에 적합한 인덱스가 다른 이유는 무엇일까?

 

 해시나 트리는 탐색 알고리즘이 아닌 데이터 구조이지만, 효율적인 탐색을 위해 사용된다. 필요한 때에 필요한 데이터를 신속하게 찾기 위해서는 데이터를 정리해둘 필요가 있다.

 

  • 필요한 때에 필요한 데이터를 빠르게 찾기 위해서 데이터를 정리해 둘 필요가 있다.
  • 데이터를 찾을 때의 데이터 구조와 데이터 저장 방식 특성에 따라 적합한 데이터 "정리 방법" 이 달라진다.
  • 데이터의 정리 방법을 데이터 구조, 찾는 방법을 탐색 알고리즘이라고 한다.
  • 처리 상대에 맞추어 데이터 구조를 정리할 필요가 있기 때문에 알고리즘과 데이터 구조는 자주 함깨 다루어진다.

 

 

 인덱스 스캔을 한다고 반드시 빨라지는 것은 아니다. 디스크에서 원하는 데이터를 얼마나 적은 노력으로 추출하느냐가 관건으로, 인덱스는 이를 위한 하나의 수단에 불과하다. 

 

 인덱스가 없는 경우에는, SQL을 발행해서 한 건의 데이터를 취득하는 경우라도 디스크에서 테이블 데이터를 모두 읽어서 조사해야 한다. 테이블의 모든 블록을 처음부터 순서대로 읽어나가는 것을 풀 스캔(full scan) 이라고 한다. 색인도 없는 사전에서 단어를 찾는 것과 같다.

 

 DBMS 인덱스로 일반적으로 사용되는 것은 B트리 인덱스다.

 

인덱스가 있으면 최소한의 필요 블록만 읽으면 된다. '인덱스'는 우리말로 '색인'이다. 사전을 찾을 때 색인을 이용하는 것과 마찬가지다.

 

 하지만 인덱스가 있다고 무조건 좋은 것만은 아니다. 검색이 빨라지는 대신에 데이터 추가, 갱식, 삭제 시에 테이블 뿐마 아니라 인덱스 데이터도 갱신해야 한다. 인덱스 갱신 때문에 불필요한 오버헤드가 발생할 수 있다. 

 

인덱스는 읽을 블록수를 줄이기 위한 수단이지만, 인덱스를 사용하면 오히려 읽을 블록수가 늘어날 수도 있다. 예를들어 테이블 데이터를 모두 취득해야 하는 경우 등이다. 이때는 테이블의 모든 블록뿐만 아니라 인덱스 블록까지 읽어야 하기 때문에 디스크 I/O 가 증가한다. 

 일반적으로 DBMS는 풀스캔을 하는 경우, 1회 디스크 I/O로 가능한 한 큰 크기의 데이터를 일겅서 I/O 횟수를 줄이려 한다. 하지만 인덱스 스캔에서는 인덱스 블록을 읽으면서 테이블 블록을 하나씩 읽기 때문에 액세스 블록 수가 늘어남과 동시에 I/O 횟수가 늘어난다.

 

 B트리가 자주 사용되는 것은, 트리 구조 계층이 깊어지지 않도록 디스크 I/O를 최소한으로 제어하기 때문이다. 반대로 인메모리 DB에서는 디스크 I/O를 신경 쓸 필요가 없기 때문에 T 트리 인덱스라는, 이진 트리의 일종을 사용하는 경우가 있다. 이진 트리는 가지가 두개 밖에 없어서 계층이 깊어지지만, 키 값 비교 횟수가 적다는 이점이 있다

 

더보기

 B트리로 이루어진 인덱스는, 루트 블록, 브랜치 블록, 리프 블록으로 분류된다.

잎 부분이 원하는 데이터 자장위치가 기록된 곳이다.

 

 

 

 데이터 구조는 데이터를 찾는 방식이나 데이터 저장 위치의 특성을 고려해서 선택할 필요가 있다. 또한, DBMS에서 인덱스를 만들면 검색은 빨라지지만 갱신 시에 오버헤드가 걸린다는 단점도 있기 때문에 함께 고려해야 한다.

블로그 이미지

맛간망고소바

,