B树
- 每个节点都保存数据
- 叶子节点之间没有指针相连
MySQL中相关的树对比分析
B+树
- 非叶子节点上不保存数据，只存关键字和指针
- 数据只保存在叶子节点的data域上
- 叶子节点之间有指针相连
MySQL中相关的树对比分析
与B树的比较
- B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
-
B+树查询速度更稳定：B树的树内存储数据，因此查询单条数据的时候，B树的查询效率不固定，最好的情况是O(1)。我们可以认为在做单一数据查询的时候，使用B树平均性能更好。但是，由于B树中各节点之间没有指针相邻，因此B树不适合做一些数据遍历操作（如JOIN操作，需要从一个表中取数据，到另一个表中逐行匹配）。
B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定。
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。因此在做数据遍历的时候，只需要对叶子节点进行遍历即可，这个特性使得B+树非常适合做范围查询（能提高JOIN操作时逐行匹配的速度）。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
与红黑树的比较
红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构，这是因为使用 B+ 树访问磁盘数据有更高的性能。
-
B+ 树有更低的树高
平衡树的树高 O(h)=O(logd N)，其中 d 为每个节点的出度。红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多。
-
磁盘访问原理
操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。
如果数据不在同一个磁盘块上，那么通常需要移动制动手臂进行寻道，而制动手臂因为其物理结构导致了移动效率低下，从而增加磁盘数据读取时间。B+ 树相对于红黑树有更低的树高，进行寻道的次数与树高成正比，在同一个磁盘块上进行访问只需要很短的磁盘旋转时间，所以 B+ 树更适合磁盘数据的读取。
-
磁盘预读特性
为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入。
b树缺点
- 随机写时，写放大严重，会耗损SSD。如极端情况下，即使只更新了一列，但也要回写整个页面（结点）
- 空间浪费严重，结点的空间利用率少于75%。
- 限定了索引的实现方式，无法使用一些高级的数据结构。
其他
磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）的最小单元是块，一个块的大小是4k，而对于InnoDB存储引擎也有自己的最小储存单元，页（Page），一个页的大小是16K。InnoDB的所有数据文件（后缀为ibd的文件），大小始终都是16384（16k）的整数倍。
InnoDB的一棵B+树可以存放多少行数据？
答案：约2千万。（高度为3时）
如何计算出非叶子节点能存放多少指针？
其实这也很好算，假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节。我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。假设一行数据大小为1k，那么一页可以存放16行。那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。
根据同样的原理可以算出一个高度为3的B+树可以存放：1170*1170*16=21902400条这样的记录。所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时，一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。
应用场景：
B/B+ 树是N叉衡树，每个节点可以有更多的孩子，新的值可以插在已有的节点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。
由于关系型数据库和非关系型数据的设计方式上的不同，导致在关系型数据中，遍历操作比较常见，因此采用B+树作为索引，比较合适。而在非关系型数据库中，单一查询比较常见，因此采用B树作为索引，比较合适。
ssd时代下，b树的存在意义？
表明优势对b树的影响
- 随机写与连续写的性能差距缩小，使得范围查询主导场景的吞吐量得到大幅提升，减小了b树在随机写场景下与其他更合适的数据结构的差距
从缺点分析
- 即使SSD的随机读性能得到了大幅提升，但是相比DRAM（内存）还是差了两个数量级。
- 有读放大问题，一次只能读一个block，至少是512b，无法像DRAM（64b）、cache（Byte级别）那样。所以还是需要b树来减少随机读次数
- 基于其它树的在SSD上实现也难有绝对的优势，在B树系列的方案中有一个特性仍然是较之其他平衡树有更好的优势，就是连续区间查询
- 价格贵
AVL树
平衡二叉搜索树：解决二叉搜索树退化成链表的情况。
基本特点：
- 具有二叉搜索树的特性
- 左右子树的高度差至多等于1
- AVL 树的每个节点需要额外两比特来表示左斜、平衡、右斜三种状态
缺点
二叉平衡搜索树的问题在于每次插入和删除都有很大可能破坏上述第2个规则，就需要重新平衡，数据就要不停的搬来搬去，在内存中这问题不是特别大，可如果在磁盘中，这个开销可能就大了。
红黑树
解决AVL在插入/删除时需要频繁的旋转操作而导致效率较低的情况。
基本性质：
- 具有二叉搜索树的特点
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点，即叶子节点不保存数据
- 不能有相邻的两个红色节点。（每个红色节点必须有两个黑色子节点）
- 每个节点，从该节点到某个可达的叶子节点的所有路径上，黑色节点的数量是一致的
性质4和性质5保证了任意节点到其叶子节点的所有路径中，最长路径不会超过最短路径的2倍。因为最短路径上都是黑色节点，而最长路径上红色节点和黑色节点交替出现，即红色节点数量=黑色节点数量，也就是是最短路径的2倍。
关于红黑树的具体插入、删除的调整操作可看此文章。
优点
- 在最坏情况下，查找的时间复杂度为
O(logN)
- 在插入/删除时，不需要像AVL那样频繁的调整。
应用场景
红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。
红黑树与AVL的对比
- 查找：两者都是对数级别，但红黑树的系数较大。如在一千万个节点的时候，AVL树保证最多需要比较34次一定能查出结果，而红黑树则最多需要比较47次。
- 插入/删除 调整（及变色）：插入调整时AVL的系数较小，而删除调整时红黑树的系数较小。插入旋转大家最多都是两次。
- 删除：红黑树保证最多旋转3次，而AVL可能是对数级别。
- 红黑树在以任意序列插入或者删除 混合进行的情况下，均摊复杂度依然保持在 O(1) 。而AVL树就惨了，可以证明存在精心构造出的特定操作序列，让它的均摊复杂度退化到 O(log(n))
参考
- 为什么Mongodb索引用B树，而Mysql用B+树?
- AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中？
- 关于 AVL 树和红黑树的一点看法
- 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了
- b-tree-原理
- 面试官：为什么MySQL的索引要使用B+树，而不是其它树？比如B树？