b-tree 와 b+tree의 차이점

둘의 가장 큰 차이는 b+tree는

• leaf node에만 데이터를 적재한다.
• 모든 node는 포인터를 갖고있다.

차이점에서 오는 쿼리

• 단일 데이터 쿼리의 경우 b-tree의 성능 효율은 고정적이지 않고 가장 최선일 경우 O(1)의 속도를 갖습니다.
  leaf 노드간의 포인터를 갖지 않기 때문에 data travel에 용이 하지 않습니다.
• b+tree 같은 경우 단일 데이터 쿼리의 경우 안정적인(고정적인) 속도를 갖습니다. 그러므로 범위 검색에 더 알맞는 모습입니다.

  leaf node의 linked list 때문에
  즉 평균 성능이 b-tree보다 낮다.

이 차이점으로 알 수 있는 것은 b+tree는 MySQL에
b-tree는 MongoDB에 어울립니다.

왜 MySQL은 data travel을 많이 하나?

그러면 왜 MySQL은 data travel을 많이하고 MongoDB는 적게하는지 궁금할 수 있습니다.

근본적으로는 MySQL은 관계형 DB이고 MongoDB는 그렇지 않기 때문입니다.

그러면 관계형 DB는 왜 data travel을 많이 하나요?

MySQL의 정규화

관계형 DB는 정규화를 통해 테이블간의 중복도를 낮춥니다.(카디널리티를 높이다.)

A 테이블과 B 테이블이 관계를 갖고 있는 상태를 가정 할 때
A 테이블의 어떠한 data로 B 테이블을 참조를 하는 경우(JOIN) data travel이 발생 하게 됩니다.

SELECT * 
FROM t_student t1, 
	( SELECT cid FROM t_class WHERE cname = '1 class ' ) t2 
WHERE t1.cid = t2.cid;

또는

SELECT s.*, c.* FROM t_student AS s,
JOIN t_class AS c ON c.id = s.c_id
WHERE c.name = "1 class";

JOIN을 써서 발생 했다 생각 할 수 있지만

SELECT cid FROM t_class WHERE cname = '1 class';

SELECT * FROM t_student WHERE cid = ...

와 같이 따로 쿼리를 이용한 조회를 한다고 해도 결국에는 data travel이 발생한 것을 알 수 있습니다.

MongoDB도 비슷하게 되지 않나?

MongoDB도 아래와 같은 형태로 디자인 할 수 있지 않나 생각이 듭니다.
동작이 됩니다. 하지만 이것은 NoSQL의 설계에 따르지 않는 행동이므로 권장하지 않습니다.

$lookup operation을 지원하지만 자주 사용되지 않으며 아래와 같은 형태를 유지 하고 싶은 경우 관계형 DB를 사용 하는게 좋습니다.

// student 
{
  _id: 1,
  name: "student 1",
  cid: 1,
}
{
  _id: 2,
  name: "student 2",
  cid: 1,
}

// class
{
  _id: 1
  name: "학급 1"
}
{
  _id: 2
  name: "학급 2"
}

그러면 어떤 형태로?

{
  _id: 1,
  name: "학급 1",
  student: [
    {
      _id: 1,
      name: "학생 1"
    },
    {
      _id: 2,
      name: "학생 2"
    },
  ]
}

db.class.find( { name: '1 class ' } ) 같은 단일 데이터 쿼리를 사용하여 data travel이 없이 결과를 얻을 수 있습니다.

결론

데이터간 travel이 잦은 경우 B+tree를 갖는 MySQL을 사용하는게 적당하며
반대의 경우 b-tree의 MongoDB가 적절하다는 것을 알아 보았습니다.

NoSQL, SQL DB간 서로는 서로의 장점들을 모두 지원하지만 어떠한게 더 적절한가