一、前情提要
1. 因为本文章中很多时候会波及到工夫复杂度和数据结构，倡议对这方面常识不理解的同学先去学习下数据结构。
二、为什么不应用数组？（增、删、改、查）？
1. 在减少元素时，咱们须要对插入地位前面所有的元素向后挪动一位，要插入的地位越靠前，须要复制的数据也就越多，这就是为什么不应用数组的起因。
2. 至于删、改、查操作，在不思考空洞的状况下（间接设置为 Null），删除是比拟快的；对于批改和查问操作来说，在晓得下标的状况下，数组的批改和查问的工夫复杂度都是 O(1), 在不晓得下标的状况下，一般数组的工夫复杂度为 O（n），有序数组中二分查找时间复杂度为
O（logn）。
三、为什么不应用链表（增、删、改、查）？
1. 在减少元素时，咱们以双链表来举例，假如采纳尾插的话，工夫复杂度只有 O（1），还是比拟不便的。
2. 至于删、改、查操作，他们都须要找到须要“操作”的节点元素，如删除元素时咱们须要让删除节点的前一个节点指向删除节点的后一个节点、批改元素时咱们须要查找到批改的元素，这三种操作的工夫复杂度都是 O（n），这就是为什么不应用链表的起因。
四、为什么不应用哈希表（增、删、改、查）？
1. 在减少元素时，咱们并不需要像数组那样对元素向后挪动，而是放入链表中，也就是咱们通常所说的解决哈希抵触的链地址法，不思考哈希抵触的状况下，哈希表工夫复杂度为（1）
2. 至于删、改、查操作，在不思考哈希抵触的状况下，和数组相似，在晓得下标的状况下，他们的工夫复杂度为 O（1）
3. 那么为什么不实用哈希表呢？因为在应用 MySQL 的过程中，常常会应用范畴查问，因为哈希表的所有 key 都会通过哈希函数计算，而后再存放数据，原本可能有序的 key，但通过哈希函数计算出来的值就不是有序的了，所以这个时候，如果要在哈希表中进行范畴查找，就只能对整个哈希表进行遍历了，只有符合条件范畴的数据，才取出来。当咱们数据库中的数据越来越多，达到几百万甚至几千万条的时候，这个时候，对整个表的遍历是十分耗时的。
五、为什么不应用 AVL 树、红黑树?
1. 每个节点最多有两个子节点的树叫二叉树，常见的有二叉搜寻树、AVL 树、红黑树等。但他们都有雷同的问题，当有大量数据的时候，他的树的高度会十分高
2.MySQL 存储的数据最终是要落地到磁盘的，MySQL 应用程序读取数据时，须要将数据从磁盘先加载到内存后能力持续操作，所以这两头会产生磁盘 IO，而如果树太高，每遍历一层结点时，就须要从磁盘读取一次数据，也就是产生一次 IO，如果数据在树高为 20 的中央，那查找一次数据就得产生 20 次 IO，这对应用程序几乎就是灾难性的，耗时太长了。
六、为什么应用 B 树而不是用 B + 树？
1.B 树的特点是无论叶子结点和非叶子结点，它都存有索引值和数据；B+ 树的特点是只有叶子结点才会寄存索引值和数据。对于非叶子节点来说，B+ 树能存储更多的索引值（因为 B + 树并不需要存储数据）
2.B+ 树的叶子节点之间应用链表的模式进行连贯，所以当进行范畴查问的时候，很容易就能够通过链表指针查问到想要的数据了