一、平衡二叉树
1. 解决的问题
对于顺序存储的有序表在查找时可以采用二分法、插值法等查找方式，使查找的时间复杂度由 $O[n]$ 提高到了$O[log_n]$ ,但是面临的问题是，顺序存储的有序表在插入和删除元素时的效率很低，为 $O[n]$，因此如何使查找、插入和删除的的效率都很高呢？
2. 概念
平衡二叉树： 每个结点左右子树的深度差不大于1的有序二叉树。
3. 分析
因为有序的完全二叉树在查找时的时间复杂度为$O[log_n]$，而平衡二叉树和有序的完全二叉树在查找时时间复杂度相同，在插入或删除元素时只需要维护该树仍然为平衡二叉树即可，因此时间复杂度依然为$O[log_n]$，即查找时所花费的时间。
二、分块索引
1. 解决的问题
当某个数据表中的内容过多时，即使有序，也使得查询的速度不尽人意。
2. 概念
分块索引： 将数据集按照关键字范围或者某个特定的关键字进行分块，各个块之间有序，块内无序或者有序均可。
3. 使用场景
①. 按范围分块：将用户按照索引大小，每5000个分到一个块中。查找时先查找所属块，再到块内查找。
②. 电话的区号：先锁定区，再到该取的数据中去查找，从而缩小被查找的数据量。
三、哈希表
1. 解决的问题
在之前的基础上，进一步提高插入、删除、查找的效率，将时间复杂度提高到 $O[1]$ ，但是缺点在于：要查找在一定范围内的数据时时间复杂度较低。
2. 概念
哈希表： 通过Hash函数，实现关键字与存储地址之间确定一种对应关系，在增删改查的过程中，直接通过函数关系找到存储地址。但也要解决因为散列不均匀而引发的冲突问题。
使用场景
①. 对于查询效率要求比较高，但很少或者几乎不涉及到范围查找的情况。
②. 如Redis等常见key-value数据库的实现。
...
...
00:00
00:00
本文为作者原创文章，未经作者允许不得转载。