另一个名字就是二叉树索引。 1.每个节点的儿子节点都是两个，左边是比该节点小的，右边是比该节点大的，这两个索引的儿子节点同样是这种情况 2.所有的节点都是一个关键字
B- 树
我们把所有的数据进行折半块查找，比如一共100条数据。在30和60的地方分一下，存放30和60的节点就是根节点。30和60就是该节点的关键字，100也就是分成了3份，这个节点自动创建三个指针。这三份就是根节点的子节点，（敲黑板划重点，子节点的个数=关键字个数+1，没有子节点就不说了）。下面继续分，拿其中一个子节点举例，把30分成3分，10和20当成关键字，下面继续是三个子节点。。。依次类推。 如下 在这里插入图片描述
关于回表查询： 比如select a from T where b=? 如果a没有索引，那在查询的时候先得得到的是b对应这条数据所在的行数。拿着这个行数，再去表中查询这条数据，得到a字段。而拿着这个行数去得到a字段的动作，就是回表查询
我们如何避免回表查询呢，首先就是不要用 ” * “ 查询，因为这时候会默认查询的字段没有索引，必定进行回表查询。
在一张表中单独查询次数多的字段，尽量加上索引吧。但是也不能遇见一个查询字段就加索引，那样的效率会越来越低，得不偿失。毕竟任何事情都是有个度的
而这种类型就是B-树，它的所有关键字都分布在节点中。不一定就是我写的两个。 特点如下：
定义任意非叶子结点最多只有M个儿子；且M>2； 根结点的儿子数为[2, M]； 除根结点以外的非叶子结点的儿子数为[M/2, M]； 每个结点存放至少M/2-1（取上整）和至多M-1个关键字（至少2个关键字）； 非叶子结点的关键字个数=指向儿子的指针个数-1； 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树； 所有叶子结点位于同一层；
ps：k是关键字，p是指针（就是图中的箭头)，只要有子节点的 都是非叶子节点。
B-树的搜索依然是从根节点开始，对关键字序列进行二分查找，如果找到则命中。如果没有，就按照相应的范围根据指针去相应的子节点。直到命中。
所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；
有的同学就说了，那数据量大的时候不是依然会查询到最底层的叶子节点。 这就是B-树的缺点，但是相比B树来说已经高级了许多。 B+树
其实B+树与B-树相差并不大，由于B-树可能会最高级的根节点查询到最低级的叶子节点。那我们可以从叶子节点开始查啊，这就产生了B+树结构。
在每一个叶子节点做一个标记，把这些标记存起来，每次查的时候可以在查询根节点的时候从叶子节点也开始查，这样是不是就省了好多时间呢。 而这些标记就是链指针。把这些链指针存进一张表中,这个表就是稠密索引.
B*树
在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3； 在这里插入图片描述
后记：写这篇文章，其实是因为今天在一个大神开的java群中，有人问什么是回表查询，为什么会有回表查询。讨论的时候发现自己对索引一知半解，刚好下午有时间，就查资料写了这篇文章。
关于回表查询： 比如select a from T where b=? 如果a没有索引，那在查询的时候先得得到的是b对应这条数据所在的行数。拿着这个行数，再去表中查询这条数据，得到a字段。而拿着这个行数去得到a字段的动作，就是回表查询
我们如何避免回表查询呢，首先就是不要用 ” * “ 查询，因为这时候会默认查询的字段没有索引，必定进行回表查询。
在一张表中单独查询次数多的字段，尽量加上索引吧。但是也不能遇见一个查询字段就加索引，那样的效率会越来越低，得不偿失。毕竟任何事情都是有个度的
转自 作者：安卓大叔 链接：https://www.jianshu.com/p/e136ec79235c
红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。现在在脑海想下怎么实现？是不是太多情景需要考虑了？啧啧，先别急，通过本文的学习后，你会觉得，其实也不过如此而已。好吧，我们先来看下红黑树的定义和一些基本性质。
红黑树定义和性质
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
性质1：每个节点要么是黑色，要么是红色。性质2：根节点是黑色。性质3：每个叶子节点（NIL）是黑色。性质4：每个红色结点的两个子结点一定都是黑色。性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。从性质5又可以推出：
性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点图1就是一颗简单的红黑树。其中Nil为叶子结点，并且它是黑色的。(值得提醒注意的是，在Java中，叶子结点是为null的结点。)
红黑树并不是一个完美平衡二叉查找树，从图1可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。
介绍到此，为了后面讲解不至于混淆，我们还需要来约定下红黑树一些结点的叫法，如图2所示。
红黑树查找
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：
从根结点开始查找，把根结点设置为当前结点；若当前结点为空，返回null；若当前结点不为空，用当前结点的key跟查找key作比较；若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；非常简单，但简单不代表它效率不好。正由于红黑树总保持黑色完美平衡，所以它的查找最坏时间复杂度为O(2lgN)，也即整颗树刚好红黑相隔的时候。能有这么好的
红黑树插入
插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。查找插入的父结点很简单，跟查找操作区别不大：
从根结点开始查找；若根结点为空，那么插入结点作为根结点，结束。若根结点不为空，那么把根结点作为当前结点；若当前结点为null，返回当前结点的父结点，结束。若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；ok，插入位置已经找到，把插入结点放到正确的位置就可以啦，但插入结点是应该是什么颜色呢？答案是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。
嗯，插入情景很多呢，8种插入情景！但情景1、2和3的处理很简单，而情景4.2和情景4.3只是方向反转而已，懂得了一种情景就能推出另外一种情景，所以总体来看，并不复杂，后续我们将一个一个情景来看，把它彻底搞懂。
另外，根据二叉树的性质，除了情景2，所有插入操作都是在叶子结点进行的。这点应该不难理解，因为查找插入位置时，我们就是在找子结点为空的父结点的。
在开始每个情景的讲解前，我们还是先来约定下，如图8所示。
其他见原文
