mysql数据结构
分类:
文章
•
2024-03-14 19:01:05
- 为什么需要使用索引？
MySQL官方对索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构。
白话文：索引就像书的目录一样可以非常快速的定位到书的页码。
如果向mysql发出一条sql语句请求，查询的字段没有创建索引的话，可能会导致全表扫描，这样的话查询效率非常低。
- Hash算法
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
index=Hash(key)
优点:查找可以直接根据key访问
缺点: 不能进行范围查找(因为底层数据结构是散列的，无法进行比较大小)
-
平衡二叉树算法
平衡二叉查找树，又称 AVL树。 它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它 的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子 ） 不超过1。 也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。
优点:平衡二叉树算法基本与二叉树查询相同，效率比较高
缺点:插入操作需要旋转，支持范围查询(回旋效率低)，且如果树的高度越高，查询IO的次数越多
- B树
B树概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
因为B树一个节点可以对应多个元素 ，是在平衡二叉树结构中减少了树的高度，所以B树数据结构相比平衡二叉树数据结构实现减少磁盘IO的操作，范围查询效率依然不高。
- B+树 -- mysql采用的数据结构
B+树相比B树，新增叶子节点与非叶子节点关系，叶子节点中包含了key和value，非叶子节点中只是包含了key，不包含value。
所有相邻的叶子节点包含非叶子节点，使用链表进行结合，有一定顺序排序，从而范围查询效率非常高。
-
MyISAM和InnoDB中B+树的区别
MyISAM、InnoDB都使用B+Tree作为索引结构，具体实现方式不同
MyISAM索引文件和数据文件是分离的，叶子界节点的value保存的是数据的地址，然后通过地址查找数据。如下图:
InnoDB中表数据文件本身就是按B+Tree组织的一个索引结构，叶子界节点的value保存的是数据本身。如下图:
