1.1 基本内容
public interfaceCallableStatementextendsPreparedStatement
public interface PreparedStatement extends Statement
1.2 Statement与PrepareStatement的区别
创建时的区别
Statement statement = conn.createStatement();
PreparedStatement preStatement = conn.prepareStatement(sql);
执行的时候
ResultSet rSet = statement.executeQuery(sql);
ResultSet pSet = preStatement.executeQuery();
由上可以看出，PreparedStatement有预编译的过程，已经绑定sql，之后无论执行多少遍，都不会再去进行编译，而 statement 不同，如果执行多遍，则相应的就要编译多少遍sql，所以从这点看，preStatement 的效率会比 Statement要高一些
PreparedStatement是预编译的，所以可以有效的防止SQL注入等问题
PreparedStatement更胜一筹
有很多的最佳实践，你可以根据你的喜好来例举。下面是一些更通用的原则：
a）使用批量的操作来插入和更新数据
b）使用 PreparedStatement 来避免 SQL 异常，并提高性能
c）使用数据库连接池
d）通过列名来获取结果集，不要使用列的下标来获取
数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
B树：
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。
由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。
一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。
B+树：
B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。
B+树是B树的变形，它把所有的data都放在叶子结点中，只将关键字和子女指针保存于内结点，内结点完全是索引的功能。
与B-Tree相比，B+Tree有以下不同点：
1、每个节点的指针上限为2d而不是2d+1。
2、内节点不存储data，只存储key；叶子节点存储data不存储指针。
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针
例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
为什么B树（B+树）？
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
这涉及到磁盘存取原理、局部性原理和磁盘预读。
先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
综上所述，用B-Tree作为索引结构效率是非常高的。
而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。
至于B+Tree为什么更适合外存索引，原因和内节点出度d有关。
由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。
二叉搜索树:(Binary Search Tree又名：二叉查找树，二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树： 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。
红黑树是一棵二叉搜索树，它在每个结点上增加一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树没有一条路径会比其他路径长出2倍，所以红黑树是近似平衡的，使得红黑树的查找、插入、删除等操作的时间复杂度最坏为O(log n)，但需要注意到在红黑树上执行插入或删除后将不在满足红黑树性质，恢复红黑树的属性需要少量(O(log
n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。具体如何保证？引出红黑树的5个性质。
红黑树的5个性质：满足以下五个性质的二叉搜索树
插入操作：
由于性质的约束，插入的结点都是红色的。插入时性质1、3始终保持。破坏性质2当且仅当当前插入结点为根节点。变一下颜色即可。如果是破坏性质4或5，则需要旋转和变色来继续满足红黑树的性质。下面说一说插入的几种情况，约定当前插入结点为N，其父结点为P，叔叔为U，祖父为G
情形1：树空，直接插入违反性质1，将红色改黑。
情形2：N的父结点为黑，不必修改，直接插入
从情形3开始的情形假定N结点的父结点P为红色，所以存在G，并且G为黑色。且N存在一个叔叔结点U，尽管U可能为叶结点。
情形3：P为红，U为红（G结点一定存在且为黑）这里不论P是G的左孩子还是右孩子；不论N是P的左孩子还是右孩子。
首先把P、U改黑，G改红，并以G作为一个新插入的红结点重新进行各种情况的检查，若一路检索至根节点还未结束，则将根结点变黑。
情形4：P为红，U为黑或不存在（G结点一定存在且为黑），且P为G的左孩子，N为P的左孩子（或者P为G的右孩子，N为P的右孩子，保证同向的）。
P、G右旋并将P、G变相反色。因为P取代之前黑G的位置，所以P变黑可以理解，而G变红是为了不违反性质5。
情形5：P为红，U为黑或不存在，且P为G的左孩子，N为P的右孩子（或P为G的右孩子，N为P的左孩子，保证是反向的），对N，P进行一次左旋转换为情形4
删除操作比插入复杂一些，但最多不超过三次旋转可以让红黑树恢复平衡。
其他
稳定排序:插入排序、冒泡排序、归并排序、基数排序
插入排序[稳定]
适用于小数组,数组已排好序或接近于排好序速度将会非常快
复杂度：O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]
归并排序[稳定]
采用分治法
复杂度：O(nlogn) - O(nlgn) - O(nlgn) - O(n)[平均 - 最好 - 最坏 - 空间复杂度]
冒泡排序[稳定]
复杂度：O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]
基数排序 分配+收集[稳定]
复杂度： O(d(n+r)) r为基数d为位数 空间复杂度O(n+r)
树排序[不稳定]
应用：TreeSet的add方法、TreeMap的put方法
不支持相同元素,没有稳定性问题
复杂度：平均最差O(nlogn)
堆排序(就地排序)[不稳定]
复杂度：O(nlogn) - O(nlgn) - O(nlgn) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]
快速排序[不稳定]
复杂度：O(nlgn) - O(nlgn) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]
栈空间0(lgn) - O(n)
选择排序[不稳定]
复杂度：O(n^2) - O(n^2) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]
希尔排序[不稳定]
复杂度 小于O(n^2) 平均 O(nlgn) 最差O(n^s)[1<s<2] 空间O(1)
九大内部排序算法代码及性能分析参见我的GitHub
4.1 散列函数设计
直接定址法:
= a*key+b```
简单、均匀,不易产生冲突。但需事先知道关键字的分布情况,适合查找表较小且连续的情况,故现实中并不常用
DJBX33A算法(time33哈希算法
= hash*33+(unsigned int)str[i];```