链表 -> 二叉查找树 -> 平衡二叉树 -> B树 -> B+树
链表：层级等于链表长度
二叉查找树：链表优化，左子节点小于当前节点，右子节点大于当前节点，可能不均匀，极端情况下和链表一样，降低读取磁盘次数。
平衡二叉树：左右子节点的高度差不大于1，当出现大于1时，自动进行平衡调整，降低读取磁盘次数
B数（平衡树）：针对二叉树只能存储一个键值对的情况进行优化，每个节点可以存储多个键值对，每个节点拥有更多的子节点。此节点也称为页（磁盘块），mysql数据的存取以页为单位，降低磁盘次数。
B+树：
- 非叶子节点不存数据，仅存储键值。InnoDB默认大小为16KB。这样可以存储更多的键值，进一步提升效率。假设每个节点存1000个键，即1000阶。如有三层则可以存储数据量：100010001000 = 10亿。由于根节点常驻内存，因此10亿的数据里面查找某个值仅需读取2次磁盘IO。
- B+树索引存储在叶子节点，并且按顺序存储。因此排序查找、范围查找、分组查询更简单。而B树是数据存储在各节点，难以实现。
- B+树页之间是双向链表连接，叶子节点内部是单向链表连接
聚集索引：以主键作为B+树的键值，而构建的B+树索引，称为聚集索引。叶子节点存储行数据
非聚集索引：以非主键作为B+树的键值，而构建的B+树索引，称为非聚集索引。叶子节点存储主键值，查询数据需要根据主键到聚集索引里查询，称为回表查询
网友评论