认识达内从这里开始

MySQL数据库是大多数软件编程开发程序员都在学习和应用一个数据库类型，而本文我们就通过案例分析来简单了解一下，MySQL数据库为什么使用B树。

一、为什么不使用数组?(增、删、改、查)?

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+树的叶子节点之间使用链表的形式进行连接，所以当进行范围查询的时候，很容易就可以通过链表指针查询到想要的数据了

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei456学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。