|
显然这种情况不稳定的我们再选择设计上必然会避免这种情况的
平衡二叉树
平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。
使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 O(log2n)。查询id=6，只需要两次IO。
前言
国庆期间看了数据库的很多资料和书籍，这点我在总结的数据库文章里面也提过了，然后我发现我对索引的介绍不全，所以整理了一下自己的笔记，决定来个索引完整版，老规矩可能还是没我正常文章风格那么跳，但是干货一定也能让你有所收获。
索引介绍
索引是什么
-
官方介绍索引是帮助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中的HashMap，TreeMap就是Hash表结构，以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。
显然这种并不适合作为经常需要查找和范围查找的数据库索引使用。
二叉查找树
二叉树，我想大家都会在心里有个图。
（编辑：鹤壁站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
