DOM 트리를 트리 자료구조로 바라보기

웹페이지가 워드 문서와 다른 점은 마크업 언어인 HTML로 작성되었다는 점이다. 워드 문서는 작성자가 텍스트 굵기나 색상을 지정하고 이미지 파일을 삽입한다. 그래서 출판한 뒤에는 고치기가 어려운 정적인 파일이다. 이와 달리 웹페이지는 인터넷 환경에서 사용자와 소통하는 동적인 문서이다. HTML은 텍스트를 어떤 태그로 감싸는지에 따라 화면에 다르게 표현할 수 있도록 만들어졌다.

즉, HTML은 인터넷 브라우저를 위해 만들어진 파일 포맷이며, 브라우저는 HTML 문서의 태그를 인식해 사용자가 볼 수 있도록 적절하게 그려내는 기능을 가지고 있다. 브라우저는 HTML 문서를 읽을 때, 각 태그 요소들을 추출해서 나무 형태로 재조립한다. 이렇게 만들어진 나무를 DOM 트리라고 부르며, 트리는 자료구조의 일종이다. 오늘은 이러한 DOM 트리를 트리 자료구조의 측면에서 살펴보고자 한다.

DOM 은 html의 계층구조를 표현하는 자료구조 MDN Web Docs >

프로그래밍 세계에서 자료구조란 데이터를 저장할 형태를 유형화해둔 것이다. 트리 구조는 서로 순서는 없지만, 계층 관계가 있는 데이터들을 표현하기에 적합한 자료구조이다. HTML 태그들은 상위 태그가 하위 태그를 감싸는 형태로 이루어져 있고, 이 관계를 계층 관계로 볼 수 있다. 이런 식으로 계속 위로 올라가다 보면, 가장 상위에 위치한 태그인 태그에서 추출된 노드가 바로 DOM 트리의 루트 노드가 된다.

blog.10pines.com >

웹 개발은 브라우저에 DOM 트리를 그리면서 시작된다. 프로그래머는 DOM의 노드를 탐색하고, 새로 삽입하거나 삭제하면서 웹페이지를 그려 나간다. 브라우저는 자바스크립트나 파이썬 같은 프로그래밍 언어가 DOM의 노드에 접근할 수 있도록 DOM API를 제공한다.

DOM의 각 노드들은 부모 노드의 속성을 상속받고, 자기만의 고유 속성인 id, class도 가지며 프로그래머가 추가하는 새로운 속성들도 얼마든지 더 가질 수 있다. DOM을 조작할 때 속성은 쓰임새가 많고 대표적으로 특정 노드를 탐색할 때 사용된다. DOM API 메서드 중에서 노드 탐색에 쓰는 API로는 queryselector 와 getElementById 메서드가 있다. 이 메서드들에 파라미터로 속성을 넘겨주면, 해당 속성을 가진 노드를 찾아서 반환해준다.

예를 들어, 만약 html 문서에 main-wrapper라는 이름의 클래스를 가진 노드가 존재한다면, 이런 식으로 찾아낼 수 있다.

document.querySelector(".main-wrapper"); // … grid … flex … … flex

또한 content라는 id를 가진 노드는 이런 식으로 찾아낼 수 있다.

document.getElementById('content') // … flex

id와 class에는 중요한 특징이 있는데, 그건 바로 id는 고유해야 하지만 class는 공유될 수 있다는 것이다. 가령 main-wrapper라는 이름의 클래스를 가지는 노드의 개수가 두 개 이상 혹은 그보다 훨씬 더 많을 수 있다. 그렇다면 여러 노드가 동일한 클래스를 가지고 있는 상황에서, querySelector로 찾아오는 노드는 그중에 무엇일까? 그리고 어떻게 항상 그 값이 같을 것이라고 확신할 수 있을까?

DOM 트리의 탐색 DOM 트리의 순회는 트리 자료구조의 순회 방법을 따른다. 트리의 노드들은 정해진 순서가 없기 때문에 탐색하는 방향이 정해져 있지 않다. 다만 자료구조의 목적은 자료를 효율적으로 탐색하고, 삽입이나 삭제할 수 있는 구조로 저장하는 것이다. 트리구조 역시 자료구조이기 때문에 효율적인 탐색 방법이 존재한다. 트리를 효율적으로 탐색하기 위해서는 타깃 노드에 도달할 때까지 최소한의 노드들을 거쳐가야 한다. 가령 불필요하게 여러 번 방문하는 노드가 없어야 하는 것이다. 이를 위해 트리를 탐색하는 과정에는 현재 방문한 노드를 기록하는 과정이 포함되어 있다.

트리 자료구조의 노드를 탐색하여, 원하는 타깃을 찾아내는 방법에는 깊이 우선 탐색과 너비 우선 탐색이 있다. 깊이 우선 탐색 방법은 루트 노드로부터 계속해서 자식 노드로 내려가며 탐색하다가 마지막 자식 노드에 도달했을 때, 만약 아직 타깃을 찾지 못했다면 다시 부모 노드로 올라가서 부모의 다른 자식 노드들을 탐색한다. 이 과정을 모든 노드를 다 방문할 때까지 반복하는 방법이다.

한편 너비 우선 탐색 방법은 루트부터 시작해서 같은 레벨의 노드들을 왼쪽에서 오른쪽으로 탐색하고, 그 아래 레벨로 내려가서 탐색하기를 반복하는 방법이다. 트리에서 레벨이란 루트부터 어떤 노드까지 도달하는 데 지나가야 하는 간선의 개수를 뜻한다. 가계도에 비유하자면, 같은 항렬의 친척들은 서로 같은 레벨의 노드이다.

미디엄 >

MDN 문서 에 따르면, queryselector와 getElementByI는 깊이 우선 탐색 방법을 채택하고 있다. 깊이 우선 탐색에서는 방문 히스토리를 기록하면서 탐색해 나가고, 타깃 노드를 찾는 순간 탐색은 종료된다. queryselector API는 해당 속성을 가진 첫 번째 노드를 찾아 반환하도록 설계되었기 때문에, DOM 트리는 노드를 탐색하다가 방문 히스토리에 아직 타깃 노드를 방문한 이력이 없고, 처음으로 타깃 노드가 발견되면 바로 탐색을 종료한다. 때문에 언제나 첫 번째 노드가 리턴될 것이라고 확신할 수 있다.

그런데 여기에서 한 가지 의문점이 생긴다. id 속성은 고유하므로 해당 id를 가진 노드는 하나밖에 없을 텐데, 굳이 매번 전체 트리를 탐색해야 하는 것일까? 혹시 이 부분을 최적할 수는 없을까? 브라우저를 구동하는 엔진인 웹킷에 관한 문서 에 따르면, getElementById에는 해시테이블이라는 자료구조가 적용되어 있다고 설명하고 있다. 해시테이블은 키와 값을 일대일로 매핑하여, 키가 입력되면 그에 대응되는 값을 곧바로 반환해 매우 빠른 탐색 속도를 보여준다.

즉 getElementById의 경우, 고유한 id를 가지고 탐색하는 것이므로 트리를 탐색하기 전에 미리 만들어져 있는 해시테이블을 우선적으로 탐색한다. 그리고 찾는 id에 대응되는 노드를 발견하면 빠르게 반환하고, 찾지 못했다면 깊이 우선 탐색으로 노드를 찾아주는 것이다.

queryselector 와 getElementById API는 모두 웹페이지 상의 특정 태그에 접근하기 위해 사용할 수 있는 메서드이고, 깊이 우선 탐색 방식으로 탐색을 수행한다. 깊이 우선 탐색의 시간 복잡도는 최악의 경우 모든 정점을 방문해야 하므로 결코 빠르다고 할 수 없다. 다만, getElementById에서는 깊이 우선 탐색을 하기 이전에, 미리 id와 그에 대응되는 노드가 저장되어 있는 해시 테이블을 사용하기 때문에 찾는 속도가 훨씬 더 빠르다.

그러므로 시간만 고려한다면 getElementById 가 queryselector보다 훨씬 좋은 메서드라고 할 수 있다. 하지만 탐색 속도는 getElementById가 더 빠를지라도, queryselector를 이용하면 여러 가지 속성들을 자유롭게 활용하고, 노드를 탐색할 수 있어서 유연하기 때문에 메서드 확장성 면에서 장점이다. 따라서 이 두 메서드는 목적에 맞게 활용하는 것이 좋다.

DOM 트리와 가상 DOM 한편, 웹페이지의 규모가 점차 커짐에 따라 페이지 리로딩에 걸리는 시간도 늘어나게 됐다. 가상 DOM 개념이 도입되었지만, 가상 DOM이 기존 DOM을 대체한 것은 아니다. DOM 트리의 요소에 직접 접근해서 바꾸는 것은 트리 구조의 탐색 기법을 따르므로 수행 시간이 특별히 길지는 않다. 브라우저는 바뀐 DOM 구조의 요소들을 배치할 위치와 스타일 요소를 새로 계산하는 과정을 거치기 때문에, 이 연산이 늘어나면서 페이지 리로딩이 오래 걸리는 상황이 발생한다.

리액트와 vue.js에서 도입한 가상 DOM은 바로 이 연산과정을 줄이기 위해 고안되었다. 가상 DOM은 DOM의 사본을 저장하는 자바스크립트 객체이다. 특정 요소에 업데이트가 발생하면 기존 DOM 과 새로 만들어진 가상 DOM을 비교하여, 변경된 요소들만 DOM에 한꺼번에 리렌더한다. 즉, DOM 트리는 트리 구조의 장점을 바탕으로 빠르고 좋은 성능을 보이는 자료구조다. 브라우저는 예전부터 지금까지 이러한 DOM 트리를 기반으로 화면을 표현하고 있다.

DOM 트리를 트리 자료구조로 바라보자 트리는 계층적으로 연결된 데이터들을 표현하기에 적합한 자료구조이다. 제목과 내용으로 이루어진 텍스트 문서를 웹 페이지에 표시하기 위해, 고안된 HTML 언어는 문단과 문장의 종속관계를 태그로 표현함으로써 계층적인 속성을 갖게 되었다. 그렇기에 트리 구조로 표현하기에 매우 적합했을 것이다.

오늘날의 브라우저는 DOM 트리뿐 아니라 CSS 요소들을 가진 CSSOM 트리, 화면에 표시할 요소들을 가진 렌더 트리를 생성한다. 즉, 브라우저의 모든 요소들은 서로 계층적인 관계로 표현되어 있고, 하위 요소는 상위 요소에 종속적이다. 렌더링 효율을 높이고자 DOM에 꼭 필요한 내용만 새로 업데이트할 목적으로 가상 DOM을 사용하는 웹 프레임워크들이 생겨났지만, 그럼에도 DOM은 여전히 html 데이터를 가장 잘 관리할 수 있는 트리구조로서 웹의 뼈대 역할을 하고 있다.