mysql索引
1.索引的分类
2.btree和b+tree
2.1 btree定义
btree是一种平衡的多路查找树，树中结点最大的孩子数目称为B树的阶，通常记为m，一颗m阶B树或为空树，或满足一下特性的m叉树：
- 树中每个结点至多有m棵子树。（即至多含有m-1个关键字）
- 若根结点不是终端结点，则至少有两棵子树。（至少一个关键字）
- 除根结点外的所有非叶结点至少有⌈m/2⌉（向上取整）棵子树
- 所有的叶子结点出现在同一层次上，等于树的高度h
- 非叶子结点结构：
2.2 b+tree
- 在B+树中，具有n个关键字的结点含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有（n+1）棵子树。
- 在B+树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉-1≤n≤m-1（根结点：1≤n≤m-1）。
- 在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
- 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。
2.3区别
在B+树中，搜索键可以重复，B树中叶子结点关键字和其他结点包含的关键字不能重复。
B+树允许将数据仅存储在叶子节点中，而B树则在叶子节点和内部节点中都存储数据。
在B+树中，存储在叶子节点上的数据使得搜索更有效，因为我们可以在内部节点存储更多的键 降低了B+Tree的高度，从而可以减少磁盘io的次数
从B+树中删除数据更容易且耗时较少，因为我们只需要从叶子节点中删除数据。
B+树中的叶子节点是链接在一起的，这使得范围搜索操作更有效且快速。
2.3 构建一个b树和b+tree
使用 50，20，30，70，60，68，52，55 构建一个3阶的b树和b+tree的过程
btree 构建过程
b+tree构建过程
3.索引数据结构和数据查找
3.1 最小存储单元
磁盘扇区、文件系统、InnoDB 存储引擎都有各自的最小存储单元。
- 磁盘上，存储数据最小单元是扇区，一个扇区的大小是 512 字节。
- 文件系统(例如EXT4),最小单元是块 (block)，一个block 块的大小是 4k。
- InnoDB 存储引擎 的最小储存单元——页(Page)，一个页的大小是 16K。
3.2 树的查找流程
磁盘的读取
首先所有磁头位于0柱面（也就是0磁道）0号磁头开始工作，目标扇区旋转到磁头下，从001->002->……->N（N为每磁道扇区数）至此，读完一个磁道。
接下来，磁头位置不动，通过电子转换开关，使1号磁头工作，所读取扇区为：011->012->……->01N
再变换磁头，直到所有盘片上的同一磁道读完：……0M1->0M2->……0MN
数据表中的数据都是存储在页中的
假设一行数据的大小是1k，
那么一个16K页，可以存放16行这样的数据。
B+ 树的叶子节点存储真正的记录，对应的文件系统 page页面，可以叫做 数据页
B+ 树的非叶子节点存放的是键值 + 指针，其对应的文件系统 page页面，可以叫做 索引页
每个节点都会占据一页，而页的大小可以通过配置来调整。
InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针， 2、页内的记录是有序的，所以可以使用二分查找在页内到下一层的目标页面的指针
-
从根页开始，首先通过非叶子节点的二分查找法。
- 确定数据在下一层哪个页之后，一层一层往下找，一直到叶子节点， 进而在叶子节(数据页)中查找到需要的数据。
对于上面b+tree如果要找55这个数据 MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，假设其他页不在内存中，所以对于根结点直接通过二分查找，判断需要加载下一个页即52所在的页（第一次磁盘io）
然后在加载52，55所在的叶节点所在页（第二次磁盘io）
3.3 3阶的b+tree能存储的数据量
InnoDB 数据页结构
我们假设主键的类型是 BigInt，长度为 8 字节， 而指针大小在 InnoDB 中设置为 6 字节，这样一个单元，一共 14 字节。
这样的话，一页或者说一个非叶子节点能够存放 16384 / 14=1170 个这样的单元。 也就是说一个非叶子节点中能够存放 1170 个指针，即对应 1170 个叶子节点。
那么对三阶的来说非叶子结点可以存放1170*1170个指针。假设每条记录的大小为1kb 16kb去掉数据页其他站用大概可以存储15条记录，则 估计的存的数据量为 1170*1170*15=20533500。 大概2千万数据
分享到：