📒 데이터베이스
데이터베이스는 정해진 방식으로 조직화된 데이터 모음이다. 데이터베이스 관리 시스템은 데이터베이스에 정보를 저장하고 읽어올 수 있게 해주는 프로그램이다. 데이터베이스는 B트리라는 데이터 구조를 활용한 시스템이다. B트리는 균형 트리이지만 2진 트리는 아니다. B 트리는 균형 2진 트리보다는 공간을 덜 효율적으로 사용하지만 성능이 더 낫고, 특히 디스크에 데이터를 저장할 때 균형 2진 트리보다 더 성능이 좋다.
이름을 알파벳순으로 저장하는 균형 2진 트리가 있다고 했을 때 위 그림과 같다.
B트리 노드에는 2진 트리 노드보다 더 많은 가지가 있다. 가지의 수는 디스크 블록 하나를 정확히 꽉 채울 수 있는 숫자로 결정된다. 위 그림 중 B 트리를 보면 내부 노드는 균형이 잡혀 있고 이로 인해 검색 시간을 미리 예측할 수 있다. B 트리를 보면 공간만 차지하는 사용하지 않는 자식 링크가 있다. 사용할 수 있는 자식 링크가 없으면 각 노드가 담당하는 범위를 조정하면서 쉽게 트리의 균형을 다시 잡을 수 있다.
노드에 저장하는 키 수가 더 많으면 노드를 디스크에서 더 적게 읽어올 수 있다. 노드의 크기가 커져도 디스크 블록에 들어맞기 때문에 아무 문제가 되지 않는다. 어차피 디스크에서 데이터를 읽어올 때는 한 블록을 한 덩어리로 읽어오기 때문이다. 사용하지 않은 자식 링크로 인해 낭비되는 공간이 있지만 이런 비효율성은 합리적인 트레이드 오프라 할 수 있다.
📒 인덱스
정렬된 데이터에 접근하면 효율적이지만 저장된 데이터를 여러 가지 방법으로 접근해야할 수도 있다. 예를 들어 이름과 성을 기준으로 데이터에 접근할 수도 있지만, 이름과 더 선호하는 가수를 기준으로 데이터에 접근할 수도 있다. 위 그림처럼 구성된 노드를 보통 주 인덱스라고 부른다. 하지만 인덱스가 둘 이상일 수도 있다. 인덱스가 여럿이면 다양한 방법으로 원하는 데이터를 효율적으로 검색할 수 있다.
📒 데이터 이동
프로그램은 한 지점에서 다른 지점으로 데이터를 이동시키기 위해 많은 시간을 소비한다. 따라서 이를 효율적으로 하는게 중요하다.
위 그림은 length 바이트 수만큼의 메모리를 모두 0으로 설정한다.
이 알고리즘은 잘 작동하지만 효율적이지는 않다. 루프 언롤링 기법을 사용하면 아래 그림과 같이 이 코드를 더 효율적으로 만들 수 있다.
더 일반적인 구현이 있으면 좋을 것 같은데 실제로도 더 일반적인 구현이 있다. 캐나다 프로그래머인 톰 더프는 영화 제작사 루카스필름에서 일하는 동안 데이터 복사를 빠르게 해주는 더프의 장치를 발명했다. 더프의 장치는 루프를 여덟 번 펼치고 남은 바이트 수에 따라 적당한 위치부터 펼친 루프의 단계를 시작한다. 루프를 더 펼치고 싶은 유혹이 있지만 이런 접근 방식이 제대로 작동하려면 언롤한 코드가 명령어 캐시 안에 유지돼서 성능을 최대한 발휘할 수 있도록 적절히 균형을 잡아야만 한다.
📒 벡터를 사용한 I/0
시스템 성능에 있어 데이터를 효율적으로 복사하는 것이 중요하다. 하지만 복사를 아예 피할 수 있으면 성능을 더 높일 수 있다. 운영체제와 사용자 공간 프로그램 사이에는 데이터가 아주 많이 오고 간다. 그리고 이런 데이터가 연속적인 메모리에 위치하지 않는 경우도 자주 있다.
예를 들어, mp3 형식의 오디오 데이터를 생성해 오디오 장치에 보내고 싶을 때, 다른 파일 형식과 마찬가지로 mp3 파일은 여러 프레임으로 구성되며, 각 프레임은 헤더와 데이터로 구성된다. 아래 그림처럼 전형적인 오디오 파일에는 헤더가 똑같은 프레임이 다수 존재한다.
모든 데이터를 한 버퍼로 복사해서 프레임을 만들 수도 있다. 하지만 그 후 이 데이터를 오디오 장치에 써야 하기 때문에 또 한번 데이터를 복사해야 한다. 대신에 프레임을 이루는 각 부분을 별도로 기록할 수도 있지만 이런 방법을 쓰면 문맥 전환 비용이 늘어나고, 프레임 중 일부만 오디오 장치에 기록된 경우 오디오 장치가 문제를 일으킬 수도 있다.
이럴 때 시스템에게 프레임의 각 부분을 가리키는 포인터의 집합을 전달하고, 시스템이 오디오 장치에 데이터를 쓸 때 각 부분을 하나로 합쳐주면 더 효율적이다.
위 그림의 아이디어는 크기와 데이터에 대한 포인터로 이뤄진 벡터를 운영체제에 넘기는 것이다. 운영체제는 이 벡터에 저장된 데이터를 사용해 순서대로 오디오 프레임을 조합한다. 데이터를 쓸 때와 읽을 때 모두 벡터를 사용할 수 있다. 벡터를 활용해 데이터를 쓰는 행위는 여러 위치에서 데이터를 모아서 쓰므로 수집이라고 부르고, 벡터를 사용해 데이터를 읽는 행위는 여러 위치로 데이터를 분산시키므로 분산이라고 부르며, 둘을 아울러 분산/수집이라고 부른다.
