西安大型网站制作,郴州招聘网,网站开发文档怎么写,wordpress所有栏目循环输出一、索引介绍
索引是什么
官方介绍索引是帮助MySQL高效获取数据的数据结构。更通俗的说#xff0c;数据库索引好比是一本书前面的目录#xff0c;能加快数据库的查询速度。
一般来说索引本身也很大#xff0c;不可能全部存储在内存中#xff0c;因此索引往往是存储在磁盘…
一、索引介绍
索引是什么
官方介绍索引是帮助MySQL高效获取数据的数据结构。更通俗的说数据库索引好比是一本书前面的目录能加快数据库的查询速度。
一般来说索引本身也很大不可能全部存储在内存中因此索引往往是存储在磁盘上的文件中的可能存储在单独的索引文件中也可能和数据一起存储在数据文件中。
我们通常所说的索引包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等没有特别说明默认都是使用B树结构组织多路搜索树并不一定是二叉的的索引。
索引的优势和劣势
优势可以提高数据检索的效率降低数据库的IO成本类似于书的目录。
通过索引列对数据进行排序降低数据排序的成本降低了CPU的消耗。
被索引的列会自动进行排序包括【单列索引】和【组合索引】只是组合索引的排序要复杂一些。
如果按照索引列的顺序进行排序对应order by语句来说效率就会提高很多。
劣势索引会占据磁盘空间
索引虽然会提高查询效率但是会降低更新表的效率。比如每次对表进行增删改操作MySQL不仅要保存数据还有保存或者更新对应的索引文件。
二、索引类型
主键索引索引列中的值必须是唯一的不允许有空值。
普通索引MySQL中基本索引类型没有什么限制允许在定义索引的列中插入重复值和空值。
唯一索引索引列中的值必须是唯一的但是允许为空值。
全文索引只能在文本类型CHAR,VARCHAR,TEXT类型字段上创建全文索引。字段长度比较大时如果创建普通索引在进行like模糊查询时效率比较低这时可以创建全文索引。 MyISAM和InnoDB中都可以使用全文索引。
空间索引MySQL在5.7之后的版本支持了空间索引而且支持OpenGIS几何数据模型。MySQL在空间索引这方面遵循OpenGIS几何数据模型规则。
前缀索引在文本类型如CHAR,VARCHAR,TEXT类列上创建索引时可以指定索引列的长度但是数值类型不能指定。
其他按照索引列数量分类单列索引、组合索引
组合索引的使用需要遵循最左前缀匹配原则最左匹配原则。一般情况下在条件允许的情况下使用组合索引替代多个单列索引使用。
索引的数据结构
三、Hash表
Hash表在Java中的HashMapTreeMap就是Hash表结构以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高时间复杂度为O(1)但是不支持范围快速查找范围查找时还是只能通过扫描全表方式。
显然这种并不适合作为经常需要查找和范围查找的数据库索引使用。
四、二叉查找树
二叉树我想大家都会在心里有个图。
二叉树特点每个节点最多有2个分叉左子树和右子树数据顺序左小右大。
这个特点就是为了保证每次查找都可以这折半而减少IO次数但是二叉树就很考验第一个根节点的取值因为很容易在这个特点下出现我们并发想发生的情况“树不分叉了”这就很难受很不稳定。
显然这种情况不稳定的我们再选择设计上必然会避免这种情况的
平衡二叉树
平衡二叉树是采用二分法思维平衡二叉查找树除了具备二叉树的特点最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡不会出现左子树很高、右子树很矮的情况。
使用平衡二叉查找树查询的性能接近于二分查找法时间复杂度是 O(log2n)。查询id6只需要两次IO。
就这个特点来看可能各位会觉得这就很好可以达到二叉树的理想的情况了。然而依然存在一些问题
时间复杂度和树高相关。树有多高就需要检索多少次每个节点的读取都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。磁盘每次寻道时间为10ms在表数据量大时查询性能就会很差。1百万的数据量log2n约等于20次磁盘IO时间20*100.2s
平衡二叉树不支持范围查询快速查找范围查询时需要从根节点多次遍历查询效率不高。
