React Diffing Algorithm

< React Diffing Algorithm >
-비교알고리즘

-diffing 알고리즘은 heuristics 알고리즘의 일종이다.
-diffing 알고리즘에서는 heuristics 알고리즘을 이용한 순회를 하게 되고 변경된 결과를 업데이트 한다.
-두가지 가정을 가지고 시간 복잡도의 새로운 휴리스틱 알고리즘(heuristics)을 구현한다.
1. 각기 서로 다른 두 요소는 다른 트리를 구축할 것이다.
2. 개발자가 제공하는 key 프로퍼티를 가지고, 여러번 렌더링을 거쳐도 변경되지 말아야 하는 자식 요소가 무엇인지 알아낼수있을것이다.

 

< react가 dom 트리를 탐색하는 방법 >

-react는 기존의 가상 dom트리와 새롭게 변경된 가상dom 트리를 비교할때 트리의 레벨 순서대로 순회하는 방식으로 탐색한다.(BFS의일종)

 

#다른 타입의 dom 엘리먼트인경우
-dom트리는 각 html태그마다 규칙이 있어 아래 들어가는 자식태그가 한정적이라는 특징이있다. 자식 태그의 부모 태그 또한 정해져 있다는 특징이 있기 때문에, 부모 태그가 달라진다면 React는 이전 트리를 버리고 새로운 트리를 구축해버립니다.

#같은 타입의 dom 엘리먼트인경우
-타입이 바뀌지 않는다면 React는 최대한 렌더링을 하지 않는 방향으로 최소한의 변경 사항만 업데이트합니다. 업데이트 할 내용이 생기면 virtual DOM 내부의 프로퍼티만 수정한 뒤, 모든 노드에 걸친 업데이트가 끝나면 그때 단 한번 실제 DOM으로의 렌더링을 시도합니다.
-하나의 DOM 노드를 처리한 뒤 React는 뒤이어서 해당 노드들 밑의 자식들을 순차적으로 동시에 순회하면서 차이가 발견될 때마다 변경합니다. 이를 재귀적으로 처리한다고 표현합니다.

 

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

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>
<ul>
  <li>Connecticut</li>    //자식 엘리먼트를 처음에 추가합니다.
  <li>Duke</li>
  <li>Villanova</li>
</ul>

-만약 처음의 자식노드를 비교할때, 다르면 전부 새롭게 렌더링한다.
-그래서 key키 라는 속성이 등장했다.

 

# key키

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>
<ul>
  <li key="2014">Connecticut</li>        //key가 2014인 자식 엘리먼트를 처음에 추가합니다.
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

-효율적으로 가상 DOM을 조작할수있도록 한다. (key값이 없는 노드는 비효율적으로 동작할수있다)
-자식 노드들이 이 key를 갖고 있다면, React는 그 key를 이용해 기존 트리의 자식과 새로운 트리의 자식이 일치하는지 아닌지 확인할 수 있습니다.
-key속성을 비교하고 React는 기존의 동작 방식대로 다른 자식 엘리먼트는 변경하지 않고 추가된 엘리먼트만 변경합니다.
-key 속성에는 보통 데이터 베이스 상의 유니크한 값(ex. Id)을 부여해주면 됩니다. 키는 전역적으로 유일할 필요는 없고, 형제 엘리먼트 사이에서만 유일하면 됩니다.
-이런 유니크한 값이 없다면 최후의 수단으로 배열의 인덱스를 key로 사용할 수 있습니다. 근데 비효율적으로 동작할것이다. 
 왜냐하면 배열이 다르게 정렬되어도 인덱스는 그대로 유지되기 때문입니다. 인덱스는 그대로지만 그 요소가 바뀌어버린다면 React는 배열의 전체가 바뀌었다고 받아들일 것이고, 기존의 DOM 트리를 버리고 새로운 DOM 트리를 구축해버리기 때문에 비효율적으로 동작하는 것입니다.

---

출처

코드스테이츠