Java向，Mysql的索引系统及数据结构

我是一个从汽车行业转行IT的项目经理。
因为最近在学File和IO相关的操作，有涉及到制作简易注册表的功能，因此为了加深印象，预习实际数据库中对数据的操作。

由面试题找思路：

1、数据库中最常见的慢查询优化方式是？
加索引
2、为什么加索引能优化慢查询？
3、哪些数据结构可以提高查询速度？
4、既然这些数据结构都能优化查询速度，Mysql为何选择B+树？

页（page）是存储器的逻辑块，操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在大多数操作系统中，页大小通常为4kb，可调节），主存和磁盘以页为单位交换数据。
磁盘预读一般为页的整数倍，innnoDb默认16kb。

索引的定义

索引是帮助Mysql高效获取数据的数据结构。（类似于RAF随机访问时的指针，cursor，.seek()操作。还有wirte()操作里的offset,length的设置。但是，这种形式实时性差。）
索引储存在文件系统中。（减少IO量和IO次数是关键）
索引的文件储存形式与存储引擎有关。（比如innoDb,myISAM等）

索引文件的结构：

hash
二叉树
B树
B+树

为什么选用B+树：

1）hash即散列表是内存中用到的数据结构。

缺点：
1、耗费内存空间
2、适用于等值查询，但是当范围查询更多的时候就不适用。

2）二叉树可分为：BS树，AVL树，以及红黑树。
分享一个网站：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
可以完成数据结构可视化。

其中红黑树为终极形态，其优化了AVL树，平衡了插入和查找的复杂度，有如下性质：
性质1：每个节点要么是黑色，要么是红色。

性质2：根节点是黑色。

性质3：每个叶子节点（NIL）是黑色。

性质4：每个红色结点的两个子结点一定都是黑色。

性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

但仍有缺点：
1、深度过深，会造成io次数变多，影响数据读取的效率。

3）B树的本质是一种多叉树。

其本身就是根据磁盘读写的规则而设计，性能更优于红黑树，其多叉查找的效率更高，层数更少，IO次数更少。

4）B+树
两个特性：
第一、非叶子节点不存储数据，只放指针和关键字，大大增加整体数据存储量。
第二、叶子节点间增加双向索引，使B+树可以同时有两根指针，一根从root开始逐层查找，而另一根可以直接从叶子节点形成的有序链表直接遍历。

优点：
1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

这篇文章只涉及概念性理论，实际操作以后再说。