수억 개 중에서, 어떻게 한 개를 빨리 찾을까

정보를 담는 데도 모양이 있어요. 그 모양을 그릇이라고 불러요. 같은 데이터라도 줄로 담느냐, 표로 담느냐, 가지로 담느냐에 따라 모양이 달라져요. 그릇은 아무거나 쓰는 게 아니라 하려는 일에 맞춰 골라요. 순서대로 보고 싶으면 줄이 좋고, 이름으로 빨리 찾고 싶으면 표가 좋죠. 그리고 한 그릇은 모든 일을 똑같이 잘하지 못해요. 어떤 동작은 빠르고 어떤 동작은 느려요. 그래서 그릇을 잘 고르는 게 곧 빠른 프로그램의 시작이에요. 다음 강들에서 대표 그릇들을 하나씩 만나볼 거예요.

배열은 번호가 붙은 칸들이 딱 붙어 있는 사물함이에요. 번호만 대면 그 칸으로 곧장 점프해서 아주 빠르게 꺼내요. 리스트는 칸들이 여기저기 흩어져 있고, 각 칸이 다음 칸 주소를 적은 쪽지를 들고 있어요. 그래서 5번째를 꺼내려면 처음부터 쪽지를 따라 한 칸씩 가야 해 좀 느려요. 대신 중간에 새 칸을 끼울 땐 쪽지 두 장만 고쳐 끼우면 끝이라 쉬워요. 배열은 반대로 뒤 칸을 다 밀어야 해서 번거롭죠. 빠른 접근이 필요하면 배열, 중간 삽입이 잦으면 리스트, 이렇게 맞바꿔 골라요.

스택은 접시 쌓기예요. 위에 올리고, 꺼낼 땐 맨 위(마지막에 넣은 것)부터 나와요. 그래서 나중에 넣은 게 먼저 나오죠. 큐는 줄서기예요. 뒤에 서고, 꺼낼 땐 맨 앞(먼저 온 것)부터 나와요. 그래서 먼저 넣은 게 먼저 나오죠. 어디에 쓸까요? 방금 한 일을 거꾸로 되돌리거나 뒤로 가고 싶을 땐 스택이 딱 맞아요. 마지막 동작부터 차례로 취소되니까요. 들어온 순서대로 공평하게 처리하고 싶을 땐 큐가 맞아요. 인쇄 대기열이나 번호표처럼요. 쌓기는 나중먼저, 줄서기는 먼저먼저, 이 한 줄만 기억하면 돼요.

데이터베이스는 정보를 체계적으로 담는 거대한 창고예요. 보통 표로 정리하는데, 한 줄(행)이 한 건이고, 세로 칸(열)이 이름·나이 같은 항목이에요. 새 정보가 오면 맞는 표의 맞는 칸에 차곡차곡 넣어요. 그냥 파일에 적어 두는 것과 다른 점은 두 가지예요. 하나, 여러 정보를 한꺼번에 안전하게 담아 줘요. 둘, 수억 건 가운데서도 원하는 걸 빠르게 찾아 줘요. 그래서 많은 정보를 다룰 땐 파일 대신 데이터베이스를 써요.

데이터베이스가 무언가를 찾는 가장 단순한 방법은 처음부터 한 줄씩 끝까지 훑는 전체 검색이에요. 데이터가 적을 땐 충분히 빨라요. 하지만 건수가 수억으로 폭증하면, 훑어야 할 줄도 그만큼 많아져서 점점 느려져요. 그래서 미리 색인을 만들어 둬요. 색인은 정렬된 이름표 목록 같아서, 처음부터 다 훑지 않고 클릭 한두 번에 바로 그 자리로 점프해요. 같은 건수라도 색인은 전체 검색보다 훨씬 적은 횟수로 찾아내죠. 색인을 실제로 어떻게 만드는지(인덱스, 해시, 트리)는 다음 강들에서 이어가요.

해시는 값을 보고 계산으로 칸 번호를 정해, 그 칸에 바로 넣고 바로 찾는 방법이에요. 칸을 하나씩 훑지 않고 한 번에 도달하니 아주 빨라요. 넣을 때도 찾을 때도 같은 계산을 쓰니, 넣어 둔 칸과 찾는 칸이 딱 맞아요. 단점도 있어요. 다른 값 둘이 계산 결과가 같아 같은 칸으로 가는 충돌이 생길 수 있어요. 그땐 한 칸에 묶어 담거나 옆 칸으로 미뤄 따로 처리하면 돼요. 정리하면, 계산으로 칸을 정해 바로 찾고, 충돌은 따로 처리하는 게 해시예요.

데이터를 한 줄로 늘어놓는 대신 가지 모양으로 두면, 한 뿌리에서 가지로 갈라져 점점 내려가요. 찾는 값이 지금 칸보다 크면 한쪽 가지로, 작으면 다른 쪽 가지로 가요. 그러면 한 단계 내려갈 때마다 살펴볼 후보가 반씩 줄어요. 그래서 수천 개라도 몇 단계 만에 찾죠. 단계 수, 곧 나무의 깊이가 속도를 정해요. 데이터가 두 배로 늘어도 깊이는 한 단계만 늘어서, 아주 많아도 천천히 깊어져요. 사전을 가운데부터 펼쳐 반씩 좁히는 것과 똑같아요.

트리는 가지로 반씩 좁혀 찾을 때 빨라요. 그런데 값을 순서대로만 넣으면 가지가 갈라지지 않고 한쪽으로만 길어져, 거의 한 줄이 돼 느려져요. 균형 트리는 이걸 막아요. 넣고 뺄 때 한쪽이 무거워지면 스스로 노드 자리를 다시 잡는데, 이걸 회전이라고 해요. 회전으로 양쪽 깊이를 늘 비슷하게 맞춰 두면, 데이터가 아무리 많아져도 깊이가 천천히(log) 자라요. 그래서 항상 몇 단계 안에 찾기를 보장해 줘요. 우리는 그냥 넣고 빼기만 하면, 트리가 알아서 균형을 지켜 줘요.

데이터가 많으면 처음부터 다 훑기는 느려요. 인덱스는 책 뒤 찾아보기처럼, 데이터베이스가 원하는 자리로 바로 점프하도록 미리 만든 지도예요. 종류가 두 가지 있어요. 해시 인덱스는 정확한 값 하나를 한 번에 콕 찾아 줘요. 트리 인덱스는 값이 정렬돼 있어서 범위를 훑어 찾기에 좋아요. 다만 공짜는 아니에요. 인덱스는 자리를 더 차지하고, 데이터가 바뀌면 인덱스도 같이 갱신해야 해요. 그래도 잘 쓰면 찾기가 훨씬 빨라져요.

그래프는 대상을 점으로, 대상 사이의 관계를 선으로 담는 자료예요. 사람을 점으로, 친구 관계를 선으로 두면 연결이 한눈에 보여요. 한 점에서 선을 따라가면 이웃이 나오고, 이웃의 선을 또 따라가면 친구의 친구가 나와요. 이렇게 선을 타고 퍼지면 연결된 무리 전체를 둘러볼 수 있어요. 추천이나 연결 찾기처럼 관계가 핵심인 일에서, 표로는 여러 번 뒤져야 할 것을 그래프에선 선만 따라가면 돼요. 정리하면, 점=대상, 선=관계, 그리고 이웃을 따라가기, 이게 그래프예요.

SQL은 데이터베이스에 원하는 걸 얻으려고 묻는 언어예요. 두 가지만 말하면 돼요. 먼저 어떤 열을 볼지 고르는 거예요. 표에는 열이 여러 개 있는데 그중 보고 싶은 열만 남겨요. 이걸 SELECT라고 불러요. 그다음 어떤 줄만 남길지 조건을 거는 거예요. 모든 줄이 아니라 조건에 맞는 줄만 남겨요. 이걸 WHERE라고 불러요. 고른 열과 거른 줄이 만나면 조건에 딱 맞는 작은 결과 표가 나와요. 표 하나를 두고 골라보기와 조건 거르기로 물으면 답이 표로 돌아오는 것, 그게 SQL의 기본이에요.

데이터는 보통 여러 표에 나뉘어 있어요. 주문은 주문 표에, 사람 정보는 고객 표에 따로 있죠. 한 표만 봐서는 표를 넘나드는 질문에 답할 수 없어요. 그래서 두 표가 함께 가진 공통 열을 찾아요. 고객번호처럼요. 그 열의 값이 같은 행끼리 짝을 맞추면, 두 표가 한 줄로 이어져요. 이렇게 이으면 한 표처럼 다룰 수 있어, 이 주문을 한 사람 이름 같은 질문에 답할 수 있어요. 정리하면, 공통 열로 행끼리 짝을 맞춰 흩어진 표를 잇는 게 조인이에요.

정규화는 한 표에 반복해 적히는 정보를 떼어 별도 표로 나누고, 공통 열로 다시 잇는 정리예요. 고객 이름을 주문마다 적는 대신, 고객은 고객 표에 한 번만 적고 주문 표에는 고객번호만 남겨요. 그러면 번호가 바뀌어도 고객 표 한 줄만 고치면 끝이라 불일치가 안 생겨요. 흩어진 줄을 일일이 고치다 빠뜨리는 일도 없고요. 단, 너무 잘게 나누면 무언가를 볼 때마다 표를 여럿 이어 붙여야 해서 느려질 수 있어요. 그럴 땐 자주 같이 보는 정보를 일부러 한 표에 합쳐 두기도 하는데, 이걸 비정규화라고 해요. 결국 반복을 떼어 나누고 관계로 잇되, 너무 잘게 나누면 다시 합치는 균형이 정규화예요.

트랜잭션은 여러 손질을 한 묶음으로 다뤄, 전부 되거나 전부 안 되게 만드는 방법이에요. 계좌 이체처럼 빼기와 더하기가 짝일 때, 둘 다 끝나야 비로소 진짜 반영해요. 중간에 전원이 꺼지거나 무언가 어긋나면, 절반만 남기지 않고 통째로 이전 상태로 되돌려요. 이걸 롤백이라고 해요. 또 여러 사람이 동시에 같은 잔액을 고치려 들면, 한 명씩 차례로 처리해 서로 덮어쓰지 않게 막아요. 한꺼번에 엉키던 일을 차례로 정리하는 거죠. 정리하면, 전부 아니면 전무, 어긋나면 롤백, 동시에도 안 꼬임. 이 세 가지가 트랜잭션이에요.

캐시는 자주 쓰는 데이터의 사본을 가까운 곳에 두는 방법이에요. 먼 저장소는 오가는 경로가 길어 느려요. 하지만 사본을 가까이 두면 다음부터는 짧은 경로로 즉시 꺼내죠. 찾는 것이 캐시에 있으면 적중이라 부르고 곧장 빠르게 꺼내요. 없으면 빗나감이라 부르고 먼 곳까지 가서 가져온 뒤, 그 사본을 캐시에 남겨 둬요. 그래서 다음번엔 적중이 되죠. 단점도 있어요. 원본이 바뀌어도 캐시에는 옛 사본이 남아, 옛 값을 내줄 수 있어요. 이걸 캐시가 오래됐다고 해요. 그래서 가끔 캐시를 새로 채우거나 일정 시간이 지나면 버려서 옛것을 막아요. 정리하면, 가까이 사본을 둬 적중하면 빠르고, 원본이 바뀌면 캐시를 새로 고치는 게 캐시예요.

압축은 같은 정보를 더 작게 담는 기술이에요. 두 가지 솜씨가 있어요. 하나는 반복을 줄이는 거예요. AAAA처럼 같은 게 줄줄이 있으면 A를 네 번이라고 적으면 짧아져요. 다른 하나는 자주 나오는 조각에 짧은 코드를 주는 거예요. 긴 조각을 짧은 기호로 바꾸면 전체가 줄죠. 그리고 압축본은 되돌리면 원본과 똑같아요. 버린 게 없으니까요. 이걸 무손실이라고 불러요. 더 세게 압축하면 더 작아지지만 압축하고 푸는 데 시간이 더 들어요. 그래서 얼마나 작게 vs 얼마나 빠르게를 맞바꿔 골라요. 정리하면, 반복을 줄이고 짧은 코드를 주어 작게 담되, 되돌리면 원본 그대로인 게 압축이에요.

데이터가 한 대로 감당 안 되게 커지면, 여러 대에 조각내 나눠 담아요. 이걸 분산이라고 해요. 각 대는 전체의 일부만 가지니, 모이면 아주 큰 데이터도 담을 수 있어요. 그리고 한 대가 죽어도 안 깨지게, 같은 데이터를 여러 대에 복사해 둬요. 이걸 복제라고 해요. 나눠 담는 분산과 복사해 두는 복제는 다른 개념이에요. 분산은 짐을 쪼개 나누는 것, 복제는 같은 짐을 여러 곳에 두는 것이죠. 이렇게 거대하고 빠른 처리를 위해, 엄격한 표 형식을 느슨하게 푼 그릇을 NoSQL이라고 해요. 해시처럼 키로 값을 바로 담고 찾는 그릇을 크게 키운 셈이라, 다음 영역인 인공지능이 다루는 어마어마한 데이터로 가는 다리가 돼요.