MySQL索引详解
索引介绍
索引是一种用于快速查询和检索数据的数据结构,其本质可以看成是一种排序好的数据结构。
索引的作用就相当于书的目录。打个比方: 我们在查字典的时候,如果没有目录,那我们就只能一页一页的去找我们需要查的那个字,速度很慢。如果有目录了,我们只需要先去目录里查找字的位置,然后直接翻到那一页就行了。
索引底层数据结构存在很多种类型,常见的索引结构有: B 树, B+树 和 Hash、红黑树。在 MySQL 中,无论是 Innodb 还是 MyIsam,都使用了 B+树作为索引结构。
优缺点
优点:
- 加快数据的检索速度,减少IO次数
- 创建唯一性索引可以保证每一行数据的唯一性
缺点:
- 创建索引和维护索引需要耗费许多时间
- 索引用物理文件存储,会耗费一定的空间
大多数情况下,索引查询都是比全表扫描要快的。但是如果数据库的数据量不大,那么使用索引也不一定能够带来很大提升
索引底层数据结构
Hash表
MySQL 的 InnoDB 存储引擎不直接支持常规的哈希索引,但是,InnoDB 存储引擎中存在一种特殊的“自适应哈希索引”(Adaptive Hash Index)
查询速度快但是不支持顺序和范围查询
二叉查找树(BST)
左边小,右边大
平衡的时候,查询的时间复杂度是O(log2(N)),平衡的时候,查询的时间复杂度是O(N),所以不稳定,不适合作为索引的数据结构
AVL树
自平衡二叉查找树,AVL 树的特点是保证任何节点的左右子树高度之差不超过 1,因此也被称为高度平衡二叉树,它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。
红黑树
自平衡二叉查找树,红黑树并不追求严格的平衡,而是大致的平衡。正因如此,红黑树的查询效率稍有下降,因为红黑树的平衡性相对较弱,可能会导致树的高度较高,这可能会导致一些数据需要进行多次磁盘 IO 操作才能查询到
红黑树的应用还是比较广泛的,TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。对于数据在内存中的这种情况来说,红黑树的表现是非常优异的
B树 & B+树
B树也称B- 树, B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced
(平衡)的意思。
B 树& B+树两者有何异同呢?
- B 树的所有节点既存放键(key) 也存放数据(data),而 B+树只有叶子节点存放 key 和 data,其他内节点只存放 key
- B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点
- B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找,可能还没有到达叶子节点,检索就结束了。而 B+树的检索效率就很稳定了,任何查找都是从根节点到叶子节点的过程,叶子节点的顺序检索很明显
- 在 B 树中进行范围查询时,首先找到要查找的下限,然后对 B 树进行中序遍历,直到找到查找的上限;而 B+树的范围查询,只需要对链表进行遍历即可
综上,B+树与 B 树相比,具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势
标签:红黑树,查询,索引,查找,MySQL,节点,详解 From: https://www.cnblogs.com/wnbzw/p/18534226