数据库为什么要使用二叉树？

看了题目，觉得很好！看了题目描述，忍不住想打人。。。

什么叫做像人一样，直接就拿出来？百万级，千万级的数量你怎么看一下就拿出来？你能做到秒级甚至毫秒级拿出数据？

我先吃颗降火药，然后这个题目我分两个来答:

1，为什么二叉树效率高？

我们都知道，现在是一个数据爆炸的时代，每天产生的数据以PB级计量，而查找数据就成了最基本的需求！

原始的查数据的方法就是顺序的比较，直到找到符合条件的数据，比如说1073741824（十亿多）这么多的数据量，顺序比较然后查找出来的次数平均为这个数的一半也就是五亿多次，而使用二叉树查找只需要log以2为底1073741824的对数，也就是30次，换句话说你只需要比较30次就可以拿到你想要的数据，五亿次和30次，你说怎么选？我们来看下两种方式的查找效率，数学表达和大O表示法

顺序查找:y＝x/2; O(N);

二叉树查找:y＝2^N;O(log2(n))

可以看到二叉树的效率为对数级别，在数学效率图上表示，就是数量级越大，效率越明显（斜率低）！

当然，二叉树只是一个普通的树结构，还有红黑树，B树等特殊二叉树！本文因为篇幅原因暂且不提！

2，为什么数据库要建索引以提高效率？

数据库建索引，其实是一种以空间换时间的方式，流量时代，速度为王！

看个栗子:

加入一张表，每行的数据大约100k，而主键的大小为0.1K，在主键上建立索引之后，除了原始数据，还需要维护一份索引数据，比如数据是100万，那么原始数据为10万m，也就是1000G，而索引大小为1G，查找索引的速度只有原始数据的1/1000，然后从索引中取出对应的原始数据所在的地址，直接寻址得到数据，可以看出用少量的索引数据换得了查找效率的大幅度提升！

①，所以数据库建索引，基本是必选的优化策略！

②，索引并不是越多越好，比如你选择了每个字段都建索引，相当于你每一行的数据都额外维护了一份，而且加上寻址地址等，数据量变为原来的2倍以上，除此之外，每次新建数据都要重新维护索引，大量的索引绝对会把系统磨死。。。

③，索引选择尽量避免重复的数据或者大量为null的数据，否则索引失效！

④，索引方式有b＋，hash等很多种方式，根据存储引擎和数据类型选择合适的索引！

关于二叉树和索引只能粗略的讲解到这了，更为详细的讲解改天挑时间再说吧，敬请关注。。。