红黑树，B树，B+树

红黑树

二叉排序树的左边比跟节点小，右边比根结点大，并且左右子树都是二叉排序树

每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

但是二叉排序树有一些极端的情况，比如每次插入的数据都是有序的，那么二叉树的结构就会退化，就会变成一个链表


所以这种情况要用平衡树，在插入的同时调整这颗树，让它尽可能的均匀分布

红黑树也是平衡树的一种，它定义了很多复杂的规则，最后就是为了保证树的平衡性


为什么要费劲心思的保证树的平衡性？

因为树的查询性能取决于树的高度，让树尽可能平衡就是为了降低树的高度

B树

B树是一种多路搜索树，他的每个节点可以拥有多余两个孩子节点，M路的B树最多能拥有M个孩子节点


像这样就是一个3路的B树，每个节点最多可以拥有3个孩子，这样进一步降低了树的高度

但是也不能把树设计成无限条路，这样就变成了一个数组了

为什么一定要用到B树？

B树主要用来做文件索引，为什么文件索引不喜欢红黑树或者数组？

因为文件系统和数据库都是存在硬盘上的，如果数据量大的话不能一次性全部加载到硬盘上。

B树是多路存储，可以每次加载B树的一个节点，然后一步步向下找

假设一个长度为10的数组


内存一次性职能加载2个树，那么长的有序数组是无法一次性加载进乃村的


如果把它设计成一个3路的B树，这样就可以每次只加载一个节点进内存


在内存中，红黑树比B树效率高，但是涉及到从盘操作，B树就更优了

mongodb就是用的b树

B+树

B+树是数据库中常用的一个索引结构,B+树的所有数据都在叶子结点，叶子结点之间还加了指针形成链表


有时候SELECT查询并不会只查询一条，而是会查询好几条，有可能会一次新查询10条，这十条数据都在叶子结点，只需要找一层就可以了

如果在B树中，就要在局部中序遍历

B+树查询的时间大概是log（n）n是树的高度

hash存储索引的话，查询的时间是o（1）

如果只选一条数据hash会更快一些，但是数据库中经常会选择多条，这个时候用B+树索引会更快一些。

而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批，并且树的高度比较低，可以提高查找效率