React Diffing Algorithm

1. React Diffing Algorithm

- 하나의 트리를 다른 트리로 변형을 시키는 가장 작은 조작 방식을 알아냈는데 조작 방식 알고리즘이 O(n^3)의 복잡도를 가지고 있었음

→ 이 알고리즘 그대로 리액트에 적용하면 너무 많은 비교 연산을 해야 하므로 리액트는 두 가지 가정을 가지고 시간 복잡도의 새로운 휴리스틱 알고리즘을 구현함 

 -- 가정 1. 각기 서로 다른 두 요소는 다른 트리를 구축할 것이다

 -- 가정 2. 개발자가 제공하는 key 프로퍼티를 가지고, 여러 번 렌더링을 거쳐도 변경되지 말아야 하는 자식 요소가 무엇인지 알아낼 수 있을 것이다.

 

 

2. React가 DOM 트리를 탐색하는 방법

React의 DOM 트리 순회 방식

- 기존의 Virtual DOM 트리와 새롭게 변경된 Virtual DOM 트리를 비교할 때, 트리의 레벨 순서대로 순회하는 방식으로 탐색

- 같은 레벨(위치)끼리 비교한다는 것은 너비 우선 탐색(BFS)의 일종이라고 볼 수 있음 

- 리액트는 이런 식으로 동일 선상에 있는 노드들을 파악한 뒤 다음 세대의 노드를 순차적으로 파악해 나감

 

2.1 다른 타입의 DOM 엘리먼트인 경우

- DOM 트리는 각  HTML 태그마다 각각의 규칙이 잇어 그 아래 들어가는 자식 태그가 한정적이라는 특징이 있음 

- 이 특징을 다르게 생각하면 자식 태그의 부모 태그 또한 정해져 있어, 부모 태그가 달라진다면 → 리액트는 이전 트리를 버리고 새로운 트리를 구축해 버림

- 이렇게 새로운 트리를 구축해 버리면 이전의 DOM 노드들이 전부 파괴 됨

<div>
	<List />
</div>

//부모 태그가 div에서 span으로 바뀝니다.
<span>
	<List />
</span>

- 이렇게 부모 노드였던 <div>가 <span>으로 바뀌어 버리면 자식 노드인 <List />는 완전히 해체 됨 

- 즉 이전의 <div> 태그 속 <List /> 는 완전히 파괴 되고 <span> 태그 속 새로운 <List />가 다시 실행 됨 

- 새로운 컴포넌트가 실행되면서 기존의 컴포넌트는 완전히 해체(Ummount) 되어 버리기 때문에 <List />가 가지고 있던 기존의 State 또한 파괴 됨!

 

2.2 같은 타입의 DOM 엘리먼트인 경우

- 반대로 타입이 바뀌지 않는다면 리액트는 최대한 렌더링을 하지 않는 방향으로 최소한 변경 사항만 업데이트 함

- 가능한 이유? 리액트가 Real DOM이 아닌 Virtual DOM을 사용해 조작하기 때문

- 업데이트할 내용이 생기면 virtual DOM 내부의 프로퍼티만 수정한 뒤, 모든 노드에 걸친 업데이트가 끝나면 그 때 단 한 번 Real DOM으로의 렌더링을 시도

- 예를 들어 래액트가 엘리먼트는 같으나 클래스 네임이 바뀐 상황에서 두 엘리먼트를 비교했을 때 스타일 속성의 컬리 속성만 다르고 나머지는 동일하다면 컬러 스타일만 수정하고 나머지 다른 요소는 수정하지 않음 

- 하나의 DOM 노드를 처리한 뒤 리액트는 뒤 이어서 해당 노드들의 자식들은 동시에 순차적으로 순회하면서 차이가 발견될 때 마다 변경함 → 이를 재귀적으로 처리한다고 표현 

* 재귀(Recursion) 처리? 자신을 정의할 때 자기 자신을 재참조 하는 것

 

2.3 자식 엘리먼트의 재귀적 처리

- 리액트는 자식 노드를 순차적으로 위에서 아래로 비교하면서 바뀐 점을 찾음

- 그렇기 때문에 리액트는 첫번째 자식 노드들과 두번째 자식 노드들이 일치하는 것을 확인한 뒤 세번 째 자식 노드를 추가함

- 이렇게 순차적으로 비교하기 때문에 맨 앞에 첫번째 노드가 바뀌어 버리면 바뀐 순간 뒤에 노드들이 같더라도 새로 렌더링 해버리므로 기대했던 성능을 낼 수 없음

→ 그래서 key 라는 속성을 지원함!

 

2.4 key(키)

<ul>
  <li key="2015">성진</li>
  <li key="2016">영현</li>
</ul>

//key가 2014인 자식 엘리먼트를 처음에 추가합니다.
<ul>
  <li key="2014">원필</li>
  <li key="2015">성진</li>
  <li key="2016">영현</li>
</ul>

- 만약 자식 노드들이 key 를 가지고 있다면 리액트는 key를 이용해 기존 트리의 자식과 새로운 트리의 자식이 일치하는 지 확인 할 수 있음

- 리액트는 key 속성을 통해 '2014'라는 자식 요소가 새롭게 생겼고, '2015','2016'를 키를 가진 요소는 그저 위치만 이동했다는 것을 알게 됨

- 이 key 속성은 보통 데이터 베이스 상의 유니크 한 값(ex. uuid)을 부여해 주면 됨

- 키는 전역적으로 유일할 필요는 없고 형제 엘리먼트 사이에서만 유일하면 됨 

 

- 만약 유니크한 값이 없다면 최후의 수단으로 배열의 인덱스를 key로 사용할 수 있음 

- 다만 배열이 다르게 정렬되면 소용이 없으므로 주의!