面试系列 mysql索引结构
数据结构介绍
红黑树
红黑树和AVL树区别
- AVL树是 严格的平衡二叉树 ，平衡条件必须满足（ 所有节点的左右子树高度差不超过1 ）。插入和删除操作会引入更多的自旋。它的高度会更低，所以 AVL树适合用于插入与删除次数比较少，但查找多的情况。
- 红黑树是 弱平衡二叉树 ，它通过着色限制的关系， 确保没有一条路径会比其它路径长出两倍， 相对于AVL树来说，它的旋转次数少，所以 对于搜索，插入，删除操作较多的情况下，我们就用红黑树 。
红黑树的性质（主要回答点）：
- 红色结点不可能相连，黑色节点可以相连
- 根节点是黑色节点
- 每个红色节点的两个子节点都是黑色，叶子节点都是黑色(Null节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 插入的点默认都是红色
B树
select * from user where user_id=100 # 索引查找
select * from user where user_id<100 and user_id>0 # 范围查找
select * from user where user_id = 100 and name = "赵云" # 联合索引查找
M阶Btree的性质：
- 结点最多含有m颗子树(指针)，m-1个关键字(存的数据，空间)（m>=2）
- 除根结点和叶子结点外，其他每个结点至少有m/2（向上取整）个子节点
- 若根节点不是叶子节点，则至少有两颗子树
插入规则
B+树
B+树特点
- 叶子节点用指针连在一起形成双向链表
- 非叶子节点仅用作索引，子节点存储数据，它的非叶子节点和叶子节点有重复元素
- 概要，关键字和Key值，数据存储的地方，双向链表
B+树存储形式/存储行数
int主键占用4个字节,指针6个字节，一个索引10个字节。一行数据1k
一页16k能放16k/10=1600个指针 16k/1k=16行数据
三层高的B+树 1600*1600*16=4千多万数据量
为什么用B+树（必背）--要结合整个演变过程的优缺点回答
Hash
mysql是提供了BTREE和HASH的索引方法
- 优点：查询性能快，只需要O(1)定位时间，只适用于等值查询
- 缺点：
- 无法进行范围查询
- 重复键会造成哈希冲突，影响性能
二叉查找树
- 优点：查找性能快，O(logn)
- 缺点：不平衡情况下会退化为链表 O(n)
时间复杂度为log(n) ,n为节点。（计算公式：时间复杂度为树的高度x：2^x=n>>x=logn）
红黑树
- 优点：保证了不会出现不平衡情况，适合用于内存型数据结构(为什么hashmap用红黑树）
- 缺点：
- 索引是存储在磁盘文件上，磁盘上的存储是随机存储，每次都需要转圈去读取一个节点，这样当 树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低效的情况
- 磁盘每次读取是读一页，一页只是为了获取一个节点的数据，也会造成性能浪费
B树
- 优点：
- 一个节点存储多个数据，更好的利用磁盘页的大小
- n叉树树的高度降低，磁盘读取次数降低
- 缺点
- 非叶节点存储数据，查询效率不稳定
- 非叶节点存储key和data指针，导致一页内能存的key数量降低，导致树的高度增高
- B树不适合做范围查询，必须用中序遍历的方法按序扫库
B+树
- 优点：
- 叶子节点用指针连在一起形成双向链表，增加了遍历的高效性
- 非叶节点不带数据，可以更高效使用索引空间
- 缺点：
- B+树的数据只出现在叶子节点上，单次查询性能不如B树
mysql使用B+树，mongo使用B树 ， 所以B树不是一无是处。
数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。