Mysql 索引的数据结构

Mysql 索引的数据结构

legegeCoder 773 2021-07-07

有序数组

数组是一种重要的数据结构,有序数组顾名思义,key是递增的,很适合等值和范围查询。

id      1   2   3   4 ....   n
name    a   b	c   d        n

假设id没有重复那么拿取id对应的name用二分法就可以实现,时间复杂度是O(logn)。优点很明显,但是缺点也很显然,如有数据的新增则需要数据移动(新申请空间、拷贝数据和释放空间等动作)

Hash

哈希表是一种以键值对(K-V)储存数据的结构,就如java中的hashmap,通过key可以get对应的value。哈希的思路是用特定的哈希函数将 K 换算到数组中的位置,然后将值 V 放到数组的这个位置。如果遇到不同的 K 计算出相同的位置,则在这个位置拉出一个链表依次存放。但是hash表支持范围查询吗?
v2-95f8ed5c13711a9c11d11945b2b8b3d9_720w

二叉搜索树

二叉树的特点:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;
    3.任意节点的左、右子树也分别为二叉查找树;
    二叉树的优势是查找和插入的时间复杂度较低
    v2-032790aff0ddf52b676413573acce776_720w
    比如我要找5,我们只需要三次就能检索到,我们要找大于5的只需要取父节点6的右子节点就可以。
    但是普通的二叉查找树有个致命缺点:极端情况下会退化为线性链表,二分查找也会退化为遍历查找,时间复杂退化为 O(N),检索性能急剧下降。
    v2-1cc416d59d4c44cf029e9e2103347bb8_720w
    当然二叉树后续又衍生出了AVL树和红黑树。

B+树

B+树可以理解为N叉树和有序数组的结合体。
v2-76d58d4d1e7eb4f9ec0ea93cf7d07c3d_720w
优点:
1.层级更低,IO 次数更少(数据库的瓶颈在于磁盘IO,层级越多磁盘IO就越多。每层拿取数据再加载到内存里,这个操作是很费时的,假如我有1000层,10000层)
2.每次都需要查询到叶子节点,查询性能稳定
3.叶子节点形成有序链表,范围查询方便


# 深入浅出mysql