B+ Tree

인내심 스토리 (2)

학부 2학년이었는지 3학년이었는지 기억이 가물가물한데, 아마도 과목 이름이 '파일 시스템' 이었고, 자료구조 과목 이후에 과목이었던 기억이다. 기말 과제로 B+ tree 를 scratch 부터 제대로 구현해서 제출하는 과제였었다. 다시 한번 이야기하지만, 넷스케이프 웹 브라우징이 가능하지 않던 시기에 외부에서의 copy.& paste 없이 구현하는 것이었다.

Workstation

집에 있는 PC 가 아니고 학교의 전산실 혹은 당시 38동 4층 어딘가에 모여 있는 UNIX 가 설치되어 있는 컴퓨터들을 이야기하는 것이었더랬다. 숙제 제출은 account 를 만들어서 e-mail 로 보내는 게 처음 시도되던 것이었고, 기본적으로 숙제는 학교에 있는 터미널에 줄 서서 혹은 삼삼오오 모여서 하는 것이었더랬다. 아침 8시 수업이었던 기억과 수업에 가기 위해 멀리서부터 터벅터벅 올라왔던 기억, 당시에는 젊은 객기에 자전거를 타고 다녀 보겠다고 오갔던 기억도 있다. 

xterm , vi 등으로 화면에 여러 개의 terminal 을 띄우는 것 자체가 신기한 경험, 주변에 고수들의 도움으로 화면이 여러 개 왔다갔다 한다든지 한글 입력이 된다든지 등이 처음 시도되었지만, 집에서 telnet 등의 도움을 받아서 할 수 있는 상황이 아직 아니어서 이 과목은 유독 늦은 밤의 기억이 많이 있다. MUD 를 만나기 전이어서 꽤 성실한 학생이었고, 순환 버스 없던 시절 신림동에서부터 터벅터벅 올라와서 퀭한 모습들의 기억은 이 때부터 시작인 듯했다.

VI + GDB

VI 를 처음 배웠었고, edit 를 거의 쓰지 않아서 지금도 :wq 를 하지 않으면 조마조마하다. 당시 많은 지인들이 Emacs 로 넘어갔지만, 나는 그 타이밍을 놓쳐 버렸고, 대신 이 때의 모든 인내심은 vi + 옆 창의 gdb 에 모여 있었다. 지금 이해하긴 힘들지만, 모든 시나리오를 손과 눈으로 미리 계산하고, 메모리 상태들을 노트에 적어 놓은 채로 내가 만들어 넣은 코드들이 제대로 동작하는지 하나씩 테스트하는 것이었다. 

unittest 의 개념을 모르던 시절이라 모든 테스트를 a.out 을 만들어서 sequence 대로 하나씩 해 보며 검증을 했었고, 이 과제의 압권은 입력으로 1000개 정도 되는 transaction 이후의 상태를 검증하기 위해 거의 모든 것을 거의 모든 노트에서 테스트했던 데 있다. 당연히(?) 처음에 1000개를 돌렸을 때 제대로 안 나왔을 거고, 디버깅이라고 해서 50개씩 끊어 손으로 만들고 내가 만든 못믿을 코드가 연습장에 적힌 대로 나오는지를 검증하는 방식... 이 때 1000개가 아니라 아예 100만개 정도 되는 입력이었으면 다른 똘똘한 방식을 고민했을까 모르겠는데, 당시는 손으로 할만한 것이었고... 인내심이 효율을 압도하던 시기였던 거 같기도 하다.

2020년대 B+ Tree

여전히 알고리즘에 끝판왕 느낌으로 존재하고 있고, MySQL / RDB 세상에서는 index 라는 이름으로 여전히 널리 쓰이고 있다. 코딩 인터뷰들에도 딱히 이걸 물어보거나 하진 않는 거 같고.. 실무에서는 이제 많은 경우 어떻게 돌아가는지는 더이상 궁금해 하지 않고, 의심 없이 쓰는 물건이 되어 버린 거 같다. 수십년이 지나도 계속 쓰는 무언가라면 그건 그 자체로도 대단하다 싶다.

부록 : AI 들에게 물어 보았다. "B+ tree 생성하는 코드를 만들어 줘"

Gemini, ChatGPT 둘 다 Python 으로 일단 보여 주는데.. 일단 Gemini는 뭔가 주루룩 내려오다가 잘렸다... --a

ChatGPT 는 뭔가 완성형 코드를 보여 주는 거 같은데..

ChatGPT 결과 화면의 아래 부분.

VsCode 에서 그대로 돌려 보니 일단 에러가 난다..

VsCode 에 Copy & Paste 후 index range error

아직 AI 가 따라 오기에 부족한 건가 라는 생각과 내가 뭘 잘못한 건가 라는 생각이 동시에 들기 시작하는 2024년이다. 영어로 물어봤었어야 하나...??