索引数据结构

索引数据结构
磁盘存储
mysql是从磁盘读取数据到内存的，是以磁盘块为基本单位的，位于同一磁盘块中的数据会被一次性读取出来，不是按需读取。以InnoDB存储引擎来说，它使用页作为数据读取单位，页是其磁盘管理的最小单位，默认大小是16kb。系统的一个磁盘块的存储空间往往没有这么大，所以InnoDB每次申请磁盘空间时都会是多个地址连续磁盘块来达到页的大小16KB。假设一行数据的大小是 1k，那么一个页可以存放 16 行这样的数据。那如果想查找某个页里面的一个数据的话，得首先找到他所在的页。

在查询数据时一个页中的每条数据都能定位数据记录的位置，这会减少磁盘 I/O 的次数，提高查询效率。InnoDB存储引擎在设计时是将根节点常驻内存的，力求达到树的深度不超过 3，也就是说I/O不超过3次。

树形结构的数据可以让系统高效的找到数据所在的磁盘块，这里就可以说一下这个b树和b+树了

B树的结构是每个节点中有key也有value，而每一个页的存储空间是16kb，如果数据较大时将会导致一页能存储数据量的数量很小。

B+Tree的结构是将所有数据记录节点按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的key 值数量，降低B+Tree的高度。B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。 B+索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般都在2～4层，这也就是说查找某一键值的行记录时最多只需要2到4次IO，这倒不错。因为当前一般的机械磁盘每秒至少可以做100次IO， 2～4次的IO意味着查询时间只需0.02～0.04秒。 数据库中的B+树索引可以分为聚集索引和辅助索引。

假设每条sql信息为1kb，主键ID为bigint型，一颗高度为2，3，4高度的B+树分别可以存储多少行数据?
因为单个页的大小为 16kb，而一行数据的大小为 1kb，也就是说一页可以存 放 16 行数据。然后因为非叶子节点的结构是：“页指针 + 键值”，我们假设主键ID 为 bigint 类型，长度为 8 字节（byte），而指针大小在 InnoDB 源码中设置为 6 字节（byte），这样一共 14 字节（byte），因为一个页可以存放 16k 个 byte，所以一个页可以存放的指针个数为 16384/14=1170 个。因此一个两层的 B + 树可 以存放的数据行的个数为：1170*16=18720（行）。

也就是说第一层的页，即根页可以存放 1170 个指针，然后第二层的每个页也可以 存放 1170 个指针。这样一共可以存放 11701170 个指针，所以一共可以存放 11701170*16=21902400（2千万 左右） 行记录。也就是说一个三层的 B + 树就可以存放千万级别的数据了。

高度为4的B+树则是 11701170117016 约等于 2000万1000，1000个 2000 万就是 200亿行的数据了。

为什么选用B+树做索引而不选用二叉树或者B树?
b 树和 b + 树应用在数据库索引，可以认为是 m 叉的多路平衡查找树，但是从理论上讲，二叉树查找速度和比较次数都是最小的，为什么不用二叉树呢？ 因为我们要考虑磁盘 IO 的影响，它相对于内存来说是很慢的。数据库索引是存储在磁盘上的，当数据量大时， 就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少 IO 次数，对于树来说，IO 次数就是树的高度，而 “矮胖” 就是 b 树的特征之一，它的每个节点最多包含 m 个孩子， m 称为 b 树的阶。 为什么不用B树呢？ b + 树，是 b 树的一种变体，查询性能更好。 b + 树相比于 b 树的查询优势：

1.b + 树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更 “矮胖”。B 树不管叶子节点还是非叶子节 点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少（有些资料也称为扇出），指针少的情况 下要保存大量数据，只能增加树的高度，导致 IO 操作变多，查询性能变低；

2.b + 树查询必须查找到叶子节点，b 树只要匹配到即可直接返回。因此 b + 树查找更稳定（并不慢），必须查 找到叶子节点；而B树，如果数据在根节点，最快，在叶子节点最慢，查询效率不稳定。

3.对于范围查找来说，b + 树只需遍历叶子节点链表即可，并且不需要排序操作，因为叶子节点已经对索引进行 了排序操作。b 树却需要重复地中序遍历，找到所有的范围内的节点。

为什么用 B+ 树做索引而不用哈希表做索引？
1、模糊查找不支持：哈希表是把索引字段映射成对应的哈希码然后再存放在对应的位置， 这样的话，如果我们要进行模糊查找的话，显然哈希表这种结构是不支持的，只能遍历这个 表。而 B + 树则可以通过最左前缀原则快速找到对应的数据。

2、范围查找不支持：如果我们要进行范围查找，例如查找 ID 为 100 ~ 400 的人，哈希表同 样不支持，只能遍历全表。

3、哈希冲突问题：索引字段通过哈希映射成哈希码，如果很多字段都刚好映射到相同值的 哈希码的话，那么形成的索引结构将会是一条很长的链表，这样的话，查找的时间就会大大增加。