数据库索引B+树查找过程：
5.2 B+Tree
B+Tree 是在 B-Tree 基础上的一种优化，InnoDB 存储引擎就是用 B+Tree 实现其索引结构。它带来的变化点：
B+树每个节点可以包含更多的节点，这样做有两个原因,一个是降低树的高度。另外一个是将数据范围变为多个区间，区间越多，数据检索越快
非叶子节点存储key，叶子节点存储key和数据
叶子节点两两指针相互链接（符合磁盘的预读特性），顺序查询性能更高
注：MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，因此力求达到树的深度不超过 3，也就是说 I/O 不需要超过 3 次。
————————————————
原文链接：https://blog.csdn.net/yy339452689/article/details/103816128
那么b树的核心是几个关键词
1. 树高:一般来说，树的高度要比二叉平衡树低很多(每个节点可以包含更多的节点)
2. 数组:每一个node，都是一个“数组”，数组是很关键的决定性因素，我们后面写入和读取分析的时候会讲到。
B+ 树单值查询
假设我们要查的值为32.
第一次磁盘 I/O，查找磁盘块1，即根节点(36,43),因为32小于36，因此访问根节点的左边第一个孩子节点
第二次磁盘 I/O, 查找磁盘块2，即根节点的第一个孩子节点，获得区间(28,32),遍历即可得32.
B+Tree相对于B-Tree有几点不同：
- 非叶子节点只存储键值信息。
- 所有叶子节点之间都有一个链指针。
- 数据记录都存放在叶子节点中。
B+树经典面试题
-
InnoDB一棵B+树可以存放多少行数据?
答：约2000万条（InnoDB一页16kb，根节点只存储主键【主键long类型8b(字节),页地址指针6b】。则：
根节点可以存储（16*1024/14）条数据（约等于1170条）
假设叶子节点一条数据1kb，而一页是16kb那么一页可以存储16条数据、
两级b+树约可以存储：1170*16
三级b+树约可以存储：1170* 1170 * 16
）
-
为什么索引结构默认使用B+树，而不是hash，二叉树，红黑树，B-树?
-
B-树和B+树的区别
答案：
为什么索引结构默认使用B+树，而不是B-Tree，Hash哈希，二叉树，红黑树?
简单版回答如下：
- Hash哈希，只适合等值查询，不适合范围查询。
- 一般二叉树，可能会特殊化为一个链表，相当于全表扫描。
- 红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。
- B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。
B-树和B+树的区别
- B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
- B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
- 查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
- B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。
详情：（MySQL索引底层：B+树详解 - 知乎 (zhihu.com)）
标签：存储,Tree,叶子,索引,磁盘,数据结构,节点 From： https://www.cnblogs.com/kkbk/p/17701925.html