데이터베이스
2진 트리는 데이터를 메모리에 저장할 때는 훌륭한 방법이지만, 메모리 안에 들어 갈수 없는 큰 데이터는 잘작동하지 않는다.
데이터베이스는 정해진 방식으로 조직화된 데이터 모음입니다. '데이터베이스 관리 시스템(DBMS)'은 데이터베이스에 정보를 저장하고 읽어올 수 있게 해주는 프로그램입니다.(mysql, mongodb등)
DBMS는 보통 맨 아래의 데이터 저장 메커니즘을 감싼 여러 계층의 인터페이스로 구성된다.
데이터베이스는 B트리방식을 사용한다. B트리방식은 2진트리는 2개의 가지를 가지는 것과 다르게 여러 가지(자식)을 가진다. B트리로하면 검색시간을 단축 시킬수 있다.
노드에 저장하는 키 수가 더 많으면 노드를 디스크에서 더 적게 읽어 올 수 있다. 한디스크에서 한 노드를 불러오는 방식이라 자식 링크가 많을수록 효율적인데, 이때 자식링크로 낭비되는 공간이 있지만 전체로 보면 합리적인 구조라 볼수 있다.
인덱스
정렬된 데이터에 접근하면 효율적이다. 하지만 저장데이터를 여러 방식으로 접근할수 있다.
인덱스가 둘이상인 데이터는 다양한 방식으로 접근이 가능하다.
인덱스의 경우 유지보수를 해야 한다는 트레이드 오프(이율배반)가 있다.
데이터가 바뀔때마다 모든 인덱스를 갱신해야하는 점이다. 하지만 데이터 변경보다 데이터 검색이 더 자주 일어나기 때문에 이러한 갱신 비용은 지불할 만 한 비용이다.
데이터 이동
배열을 사용하려면 배열의 크기를 증가 시킬때마다 데이터를 복사해야한다. 이런식으로 프로그램은 한 지점에서 다른지점으로 데이터를 이동시키기 위해 많은 시간을 소비한다.
lenth(예를 들어 5) 만큼의 메모리를 모두 0으로 설정하면 current(0으로 설정할 메모리의 맨앞 주소)가 가리키는 메모리를 한자리씩 0으로 만들고 current는 다음 데이터를 가리키고 를 반복하면서 length만큼 돌때까지 반복하고 완료한다.
이 작업을 할때 '루프 언롤링'기법을 사용하면 더 효율적으로 만들수 있다.
루프 언롤링은 length가 짝수일때 한번에 2개의 주소값을 처리하고 length값도 2개씩 빼주는 방식이다.
또 다른 방식은 더프 방식인데 루프를 8번 펼치고 남은 바이트에따라 적절한 위치부터 시작한다.
적절한 위치에 시작하는 방법은 시작할때 남은 length가 0~7 사이인지 확인하고 해당 위치일때마다 맞는 위치에서 루프를 시작하게 하는 단계를 거친다.
또 다른 효율성을 위한 방법은 64비트로 이루어진 기계라면 8바이트를 0으로 설정할수 있다는 사실을 활용한 것이다. 이 방법에서는 시작과 끝에 남는 데이터들을 처리하는 코드만 추가해주면 최대한 많은 8바이트 덩어리를 0으로 계산한다.
원본을 복사해서 복사본을 만들때는 더 복잡하다 원본과 복사본의 경계가 일치하지 않을 수 있기때문이다. 하지만 이 워드 경계가 일치하면 좀더 쉽기때문에 복사시에는 한번 워드 경계에 위치하는지 검사할 가치가 있다.
또다른 복사의 문제는 데이터가 여러개인데 같은걸 복사하는 경우나 버퍼의 위치를 조정하고 싶는등의 상황의 경우 데이터가 덮어써지는 등의 문제가 발생 할 수 있어 이를 방지 하기 위해 복사를 역방향으로 진행하기도 한다.
벡터를 사용한 I/O
시스템 성능에 있어 데이터를 효율적으로 복사하는것도 중요하지만, 복사를 피할 수 있으면 성능을 더 올릴 수 있다. 운영체제와 사용자 프로그램간에 많은 데이터가 오고가는데 이중에 데이터가 연속적으로 위치하지 않는 경우도 자주 있다.
예를 들어 mp3형식의 데이터를 생성하고 이거를 오디오 장치에 보내고 싶다고 생각하자.
이때 파일은 여러 프레임이 있고 프레임으 헤더와 데이터로 구성된다.
모든 데이터를 한 버퍼에 복사해서 프레임을 만들 수도 있다. 하지만 그 후 이 데이터를 오디오 장치에 써야하기 때문에 또 복사해야한다. 이러한 방식은 '문맥전환'비용이 늘고, 프레임중 일부만 오디오 장치에 기록된경우 오디오 장치가 문제를 일으킬수 있다.
이럴 때 시스템에게 프레임의 각 부분을 가리키는 포인터의 집합을 전달하고, 시스템이 오디오 장치에 데이터를 쓸 때 각 부분을 하나로 합쳐주면 효과적이다 ( 복사를 하지않고 프레임의 주소값을 알려주고 시스템에서 호출시 합쳐준다 )
아이디어는 크기와 데이터에 대한 포인터로 이뤄진 벡터를 운영체제에 넘기는 것이다. 이렇게 벡터를 활용해 데이터를 쓰는 행위를 '수집'이라고 하고 읽는 행위를 '분산'이라고 한다.
이 수집/분산은 인터넷에서도 활용된다. 우리가 알고 있는 'TCP/IP'에서 패킷이 올바른 순서로 전달되게 할 책임이 분산과 수집을 통해 이루어진다.
