第36讲：数据库索引结构之二叉树和红黑树的概念

1.二叉树数据结构的概念

在InnoDB引擎中主要使用的索引结构是B+tree的索引结构，下面我们先来看一看二叉树的一些概念。

在二叉树结构中，每一个节点下面只能包含两个子节点。

如下图所示，36就是整个结构中的根节点，有对应的两个子节点，左侧的节点比36小，右侧的节点比36大，此时我们想要去查询17这个数据，首先用17和根节点36进行对比，发现比36小，那么就走左侧节点，然后找到根节点下的子节点22，发现17比22子节点小，那么继续往下走左侧子节点，到了19子节点时发现17还是比它小，那么继续往下走左侧子节点，然后找到了17，一共需要走4层才能找到对应的数据。

如果维护二叉树时是顺序写入的，如右侧图，如果是按照顺序写入每一层二叉树的，那么就是单向列表，需要经过很多层才能找到我们需要的数据，相当于将整个链表进行比对搜索，效率很低。

二叉树数据结构有很大的缺点：顺序插入时，会形成一个大的链表，查询性能低，并且每个节点下只有2个子节点，如果数据量很大时ÿ