一、查找 

静态查找

无序查找：一个个对比O(n)

顺序查找：二分查找法，O(logn)。可通过将查找过程建立二叉判定树来计算时间复杂度，查找到一个元素的过程实际上就是从根节点找到目标节点的过程，比较次数即为树的深度，而根据二叉树的性质，深度为k的二叉树的结点总数为2的k次幂再-1，所以n各节点的树的深度为log(n+1)，所以时间复杂度即为深度O(logn)。

动态查找

1  二叉排序树/搜索树

是一棵左结点比根根节点小，右结点比根结点大的树，递归定义，并允许树/子树为空。

时间复杂度与二叉判定树算法一样，但上面的深度计算公式是完全二叉树的情况，二叉搜索树在最坏的情况下可能是一棵单链的树，时间复杂度为O(n)。一般情况下大约占40%多，时间复杂度还是O(logn)。所以不稳定。

2  二叉平衡树

由于二叉排序树时间复杂度的不稳定，就引入了平衡的概念，使左右子树高度之差保持在1内。插入和删除树都需要严格维持平衡状态进行大量旋转。

 1）红黑树：

    红黑树是一棵不“完全平衡”的平衡树，借助红黑树的五个性质，能保证其时间复杂度在O(logn)。

    与平衡二叉树相比，其插入时的旋转操作与AVL一样都能维持在两个旋转内，删除比AVL稳定，红黑树能保证在删除时旋转操作最多三次，而AVL有可能会导致被删节点到根节点都需要旋转，O(logn)。

    5个性质：a.节点非黑即红 b.根节点是黑色 c.所有Null成为叶子结点，也是黑色  d.所有红节点的子节点都是黑色的（不可能两个红的相连）e.任一节点到其叶子结点的所有路径上的黑节点数量相同，（最短路径==最长路径，平衡所在）

2）B树 B+树

平衡的多路查找树

二、索引

1.为啥不用平衡二叉树或红黑树？

索引是为了加快查询的速度的一种方式，索引一般都很大，因此不可能将其放在内存中，一般也是放在磁盘上。所以，在选取索引的数据结构时，要考虑的更多的是访问磁盘的I/O次数。

在树形结构中，我们访问一个节点就要做一次I/O操作，即树的深度就是我们做I/O操作的次数。而其他的树都是二叉树，无形中就限制了树的高度。所以我们采用m阶的B树（不是m叉树！！）实现，B树比一般的二叉树更加矮胖，符合我们的要求。

2.为啥用B+不用B树？

B树和B+树都是很矮胖的树。结构上有所不同

1）B树

B树满足几个性质：a.每个节点最多有m个子树，b.根节点最少两个或为叶子结点，c.其他节点最多ceil(m/2)个子树 d.任何一个节点都包含一个其0上关键字的数量，关键字和和指向子树的指针（交替），关键字顺序排序（搜索树啊）。e.所有叶子结点都在同一层上，不带任何信息。（可用来说明查找失败）

B树的每个节点包含最少ceil(m/2)个关键字以及指针（数量一致o），就是他的每个节点都是包含数据信息的，他的所有叶子结点都没有信息。

每次查找到一个节点需要做两个操作，（1）去磁盘读取数据（一个节点上ceil（m/2）） （2）在读取的几个数据中查找要找的数据。由于B树节点分支较二叉树多而矮胖，所以只需要少数的几次I/O操作即可。时间复杂度是O（log以ceil(m/2)为底 N）

2）B+树

B+树与B树有几个区别，首先B+ 树每个节点上只有关键字，我们可以将它看作索引，并且含有n个子树的节点上有n个关键字。叶子节点上包含所有信息以及指向含这些信息的指针，并且叶子结点之间依关键字大小顺序链接。

由此我们可以推出，B+树由于B树的几个地方。

    a.B树每个节点包含信息多，占空间大，导致整个索引在磁盘中占的空间会比B+树的大，当我们要加载索引进内存时，B+树就能加载的更多（一个盘快上存的更多），一次I/O操作能做更多的查询。

    b.由于B+树的叶子结点包含全部信息且按顺序相连，当有范围查找时，B+树就不需要多次读写内存了，而B树要遍历树

    c.B+树的查询更加稳定，都是在叶子节点上，比较次数每次都一样。

3 hash索引

hash索引即利用哈希表将key映射在哈希表上，冲突采用链地址法。（like hashmap结构 ）

所以哈希索引查找速度非常快了O(1)，但十分局限，只适用于等值查询较多，且重复元素较少的情况（避免冲突 链表过长）。

三、数据库优化

1）数据库设计方面

建立索引-->在SQL方面就避免使用会使索引失效的语句，比如控制查询，不等，计算操作等。

尽量使用固定长度的字段（提高性能，可直接计算出偏移量），

限制字段长度（存放在磁盘中占用空间小，可一次多读取一些），

分区（将数据存储在不同磁盘，查找去对应磁盘找，表还是一个表）、主从，分表分库

2）数据库I/O方面

增加缓冲区、

若涉及表的的级联，将不同的表存储在不同的磁盘上，以增加I/O速度。（并行读取吗？？？不懂）

3）SQL语句方面

关联时小表为主表、查询时筛选多的条件在前，避免select*,需要什么查什么等

限制反悔的条目数，使用分页

4）Java方面

PrepareStatement，预处理缓存

存储过程，预处理，缓存，速度快，重复代码少（不好维护）

存储过程的优缺点：

优点：a.复杂业务逻辑封装，复用

           b.将多条sql访问数据库的操作合并为一条

            c.只编译一次，不需要每次都重新编译

            d.可设置用户权限，安全性高

缺点：a.不易调试 ，难以维护，难修改

            b.可移植性差，不同数据库写存储过程语法有不同

PrepareStatement 和 Statement区别

执行静态的Sql语句，即完整的语句；prepareStatement可以包含动态参数“？”，预防SQL注入

statement每次都需要编译执行；prepareStatement会进行预编译，将命令放在缓冲区中，下次执行时就不需要在编译了，大大提高效率（jdbc存储过程）

prepareStatement支持批处理

SQL注入

SQL注入：攻击者将SQL命令通过表单输入框或页面请求查询字符串插入后台执行SQL中，欺骗服务器执行恶意SQL命令的（一般使用or 1==1）

防范：a.检查数据变量类型和格式

           b.过滤特殊符号

            c.绑定变量，使用预编译语句

            d.判断返回数据的条数