NOTE
1.10 MySQL索引底层实现
1. 索引底层实现 - 在InnoDB存储引擎中，每一个索引对应一棵B+树 2. 为什么选用B+树 首先我们先思考为什么选用树这种结构，而不是线性表或者链表 2.1. 为什么是树 - 线性表的特点是查找快O（1），但是插入删除效率低O（n） - 链表的特点是插入删除快O（1），查找慢O（n） - h
这是历史学习笔记，可能存在过时或不完整的理解。
1. 索引底层实现
- 在InnoDB存储引擎中，每一个索引对应一棵B+树
2. 为什么选用B+树
首先我们先思考为什么选用树这种结构，而不是线性表或者链表
2.1. 为什么是树
- 线性表的特点是查找快O（1），但是插入删除效率低O（n）
- 链表的特点是插入删除快O（1），查找慢O（n）
- hash表的特点是存取效率都是O（1），但是不支持范围查找
- 而树则综合了线性表和链表的特点，对查找和增删效率做了折衷，适合数据库这种频繁查找修改的场景
2.2. 为什么是B树而不是二叉平衡树
- B Tree.md（关联笔记尚未公开）
2.3. 为什么是B+树而不是B树
- B Tree.md（关联笔记尚未公开）
2.4. 总结
首先线性表 VS 链表 VS Hash表 VS 树 然后二叉搜索树 VS B类树 前者是个内存树，需要把所有数据加载到内存中才能实现O（logn）的效率，但是数据库数据很大，根本不可能。 我们只能一批批读取，磁盘IO的原理空间局部性原理，一次性读取若干Block，我们需要一种树，能一次性读取大量数据 接着B树 VS B+树 前者每个node除了key还有数据，不利于一次性读取更多的key筛选 后者最后一层存放data，连起来便于范围查找