赞
踩
索引在项目中还是比较常见的,它是帮助MySQL高效获取数据的数据结构,主要是用来提高数据检索的效率,降低数据库的IO成本,同时通过索引列对数据进行排序,降低数据排序的成本,也能降低了CPU的消耗
索引的优点:
我们都知道 Mysql 的 InnoDB 的索引使用的是 B+树,但是为什么使用 B+树呢。我们先了解一下二叉树和红黑树这两种的数据结构。
首先二叉树来说,如果在理想状态下,也就是完全二叉树的状态下,我们查找一个数据的时间复杂度是 O(logN)。
但是如果像上图一样,二叉树的数据出现了偏移,也就是树的退化现象。
当我们构建二叉树的时候插入的是有序的数据,那么就会出现树的退化。
直接后果就是,该二叉树变成了链表,查询一个数据的时间复杂度变成了 O(N),那么索引就起不到我们设计之初想让他起到的作用了(增快查询速度)。
为了解决上述的问题,有一种数据结构也就是红黑树,通过节点之间的旋转,避免了树的退化现象。
红黑树的性质: 红黑树是一棵二叉搜索树,它在每个节点增加了一个存储位记录节点的颜色,可以是 RED, 也可以是 BLACK;通过任意一条从根到叶子简单路径上颜色的约束,红黑树保证最长路径不超过最短路径的二倍,因而近似平衡。
当红黑树发生节点偏移的时候通过旋转来保证树的平衡。
但是,对于红黑树来讲如果我们的数据比较多的情况下,那么查询数据还是 O(logN)还是跟树的高度有关。我们需要尽可能的降低树的高度。
B 树是一种多叉路衡查找树。
我们假定一个 B 树的度为 5,那也就是说这棵树的节点最大可以容纳四个数据,五个指针。
这样就可以解决树的高度过高的问题,但是 B 树的每个节点上面都有数据,这对于我们排序和查找不是那么方便,那有没有更好的数据结构呢?
B+Tree 是在 BTree 基础上的一种优化,使其更适合实现外存储索引结构。
B+树的特点:在 B 树的基础上修改了以下几点:1、B+树只有叶子节点才储存数据。2、B+树的叶子节点带有指针组成一个双向循环的链表。
1、在 B 树中,非叶子节点和叶子节点都会存放数据,而 B+树的所有的数据都会出现在叶子节点,在查询的时候,B+树查找效率更加稳定
2、在进行范围查询的时候,B+树效率更高,因为 B+树都在叶子节点存储,并且叶子节点是一个双向链表
原理:在底层维护一张哈希表,通过哈希算法将键值算成hash值,映射到相应的槽位,存储在哈希表
特点:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。