B树与B+树

2-3树与2-3-4树

• 2-3树 每个节点有2个或3个指针（两个指针夹着一个关键字，三个指针夹着两个关键字）；是B树的一种，即3路查找树
• 2-3-4树 每个节点有两2个或3个指针或4个指针；是B树的一种，即4路查找树

B树

B树即多路查找树，每个节点既存储了关键字，又存储了数据。（也可能关键字本身就是数据）

B+树

B+树在B树基础上进行修改，数据都存储在叶子节点，其他节点只存储关键字。所以B+树的叶子节点包含所有的关键字和数据。
并且B+树的叶子节点之间添加了指针，将叶子节点串成了链表。这样方便读取大量数据，比如取大于某个关键字的部分，沿着链表向右取即可。

数据库索引

• MySQL数据库索引的底层是B+树
  为什么选择B+树？
  首先声明B+树的查找速度是不如B树的，因为B树的每一个节点都包含数据，所以查找到即可返回；而B+树必须查找到叶子节点

1. B+树叶子节点的存储方式有利于进行树的遍历，沿着链表即可实现子树的中序遍历，所以有利于查找大于或者小于某个关键字的数据。（这个很重要，因为计算机科学中存在着著名的局部性原理--当一个数据被调用时，存储在其附近的数据也会马上被使用）
2. 由于B树节点存储关键字+数据。而B+树非叶子节点存储的是索引关键字，MySQL中B+树的一个节点默认最大为16KB，所以相同的内存页中存储的B+树会数据会比B树更多，数据相同时，B树的深度将会更大，增大查询时磁盘I/O次数，影响效率。

• 聚集索引与非聚集索引
  聚集索引是指：整个表是按照一定的顺序来存储的，维持这个顺序的索引就是聚集索引。聚集索引只能有一个，通常是主键。如字典的拼音查找。
  非聚集索引是指：就是一个单纯的索引，也就是说，索引是按照顺序存储的，但索引对应的内容并不是。如字典的部首查找。

非聚集索引与聚集索引使用的B+树叶子节点存储的数据是不同的，聚集索引存储的就是数据本身；而非聚集索引存储的是聚集索引对应的key，查找时通过聚集索引的key再到主键索引树上获取数据，这个过程称为回表

避免回表可以采用覆盖索引的方式，比如建立两个索引，id为主键索引，name为普通索引，则当我们要利用name查找id时，name节点的数据本身就是聚集索引id，就不需要回表了。建立联合索引很多时候就是为了覆盖索引。

MySQL数据库的索引为什么用B+树实现?

• 二叉查找树，这个树在索引递增的条件下会退化成链表，不平衡
• 红黑树，也不平衡，树的高度太大，会导致查找次数过多
• B树，把红黑树的节点扩大一点，横向上面可以存储更多的元素，一次加载一个节点（MySQL默认设置一个节点的大小最大为16kb），高度就可以变低了
• B+树，改造一下B树可以得到，具体见B+树的笔记