链表的查找是不是需要从头部遍历啊，这时候和没加索引从表的第一行遍历是不是没什么太大区别？这就是mysql索引底层没有使用二叉树这种数据结构的原因之一。
当二叉树像上图一样退化成链表后，我们去查col1=6的记录是不是从二叉树的根节点依次遍历，遍历6次才能查到，和不加索引从表里一行行的遍历没太大差别。这是二叉树所谓索引底层数据结构的弊端之一。
红黑树
那有没有更好的数据结构用来存储索引，帮助我们更快的查找呢？比方说红黑树或hash表。
我们先看下红黑树。红黑树是什么？
是一种平衡二叉树，JDK1.8的hashmap就用到了红黑树。
那我们把刚才的一样的数据用红黑树来看一下是什么样的效果，同样打开刚才的网址，我们选择红黑树。
