索引选择，B+树和B树

共同结构:

两种数据类型都是小的数据在左边，大的数据在右边，拥有二分查找的效率，logn 的效率。这是平衡树的性质

B 树的结构:

b+树的结构：

1. 叶子节点存储索引和数据，中间节点不存储数据，只存储对应的索引值。 这样中间节点就够支持更多的节点，就能存储更多的数据

2.叶子节点之间用双向链表连接起来，如果需要查找 where id>10&&id<20 就可以通过叶子节点之间的双向链表实现查询。找到 id 等于 11 的节点后，向后进行遍历，这样范围查询的效率就会很高。

3.B+树在 3-4 层的时候就可以存储上千万的数据，层次低，读取的 IO 次数变少。

为什么用 B+树，而不用 B 树

1.数据量:B+树的同样高度存储的数据要 比 B 树多，因为 B+树只有叶子节点存储数据，那么非叶子节点就能存储更多的索引值，这样相同高度的 B+树存储的数据量要大于 B 树。

2.支持范围查找 并且 B+树对于排序也是支持的，叶子节点是排好序的。

3.B 树的优点：b 树因为每一个节点都存储数据，有时候可能查询的效率比 b+树更高。但是 b+树千万条数据也就是 4 次 IO 这样，能够接受。

这两种结构对比普通二叉树的优势在于，普通二叉树的层次比较高，查找每次 IO 次数都很高，数据都是存储在磁盘中的，每次 IO 那样时间太长了。

其他索引

Hash 索引，支持等值查找，不支持范围查找。

B+树能存储多大的数据

mysql 表数据增长之后的执行时间测试。千万级别的时候都是在 1 秒左右，但是到两千万的时候 sql 执行的时间就会很长。