JAVA

首先我们介绍一下一颗 m 阶B-tree的特性，那么这个 m 阶是怎么定义的呢？这里我们以一个节点能拥有的最大子节点数来表示这颗树的阶数。举个例子，如果一个节点最多有 n 个key，那么这个节点最多就会有 n+1 个子节点，这棵树就叫做 n+1（m=n+1）阶树。一颗 m 阶B-tree包括以下5条特性：

1. 每个节点最多有 m 个子节点
2. 除根节点和叶子节点，其它每个节点至少有 [m/2] （向上取整的意思）个子节点
3. 若根节点不是叶子节点，则其至少有2个子节点
4. 所有NULL节点到根节点的高度都一样
5. 除根节点外，其它节点都包含 n 个key，其中 [m/2] -1 <= n <= m-1

这些特性可能看着不太好理解，下面我们会介绍B-tree的插入，在插入节点的过程中我们就会慢慢理解这些特性了。B-tree的插入比较简单，就是一个节点至下而上的分裂过程。下面我们具体以一颗4阶树来展示B-tree的插入过程。

首先我们 插入 200，300，400，没有什么问题，直接插入就好。

| 200 | 300 | 400 |

现在我们接着插入500，这个时候我们发现有点问题，根据定义及特性1我们知道一颗4阶B-tree的每个节点最多只能有3个key，插入500后这个节点就有4个key了。

| 200 | 300 | 400 | 500 |

这个时候我们就需要分裂，将中间的key上移到父节点，左边的作为左节点，右边的作为右节点，如下图所示：

通过整个的插入过程我们也会发现，B-tree和二叉树的一个显著的区别就是，B-tree是从下往上生长，而二叉树是从上往下生长的。现在我们想想特性2和特性5是为什么？首先我们知道子节点的个数是等于key的数目+1，然后一个节点达到m个key后就会分裂，所以分裂后的节点最少能得到 m/2 - 1个key 。为啥还要减一呢？因为还要拿一个作为父节点。所以这个节点最少回拥有 m/2 - 1 + 1 = m/2 个子节点。同样得到特性5，因为最少有m/2个子节点，所以最少就含有m/2-1个key，m 阶树，每个节点存到了m个key就会分裂，所以最多就有 m-1个key。

根据以上特性我们能推出一棵含有N个总关键字数的m阶的B-tree树的最大高度h的值,

树的高度h: 1， 2， 3 ， 4 ，.......... ， h

节点个数s: 1， 2， 2*(m/2)， 2*(m/2)(m/2)， ........ ，2*(m/2)的h-2次方

s = 1 + 2(1 - )/(1- (m/2))

N = 1 + s * ((m/2) - 1) = 2 * () - 1

h = log┌m/2┐((N+1)/2 )+1

2：为什么btree/b+tree 为常用数据库索引结构？

上文说过，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。

图5

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

主存的存取过程如下：

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

磁盘存取原理

上文说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

图6是磁盘的整体结构示意图。

图6

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

图7是磁盘结构的示意图。

图7

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

B-/+Tree索引的性能分析

到这里终于可以分析B-/+Tree索引的性能了。

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B- Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

上文还说过，B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小：

dmax = floor(pagesize / (keysize + datasize + pointsize))  (pagesize – dmax >= pointsize)

或

dmax = floor(pagesize / (keysize + datasize + pointsize)) - 1  (pagesize – dmax < pointsize)

floor表示向下取整。由于B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能。

这一章从理论角度讨论了与索引相关的数据结构与算法问题，下一章将讨论B+Tree是如何具体实现为MySQL中索引，同时将结合MyISAM和InnDB存储引擎介绍非聚集索引和聚集索引两种不同的索引实现形式。

1、不同的tomcat的启动文件startup.sh 中要指定各自的CATALINA_HOME和CATALINA_BASE这两个环境变量。

2、不同的tomcat启动和关闭监听不同的端口

很多人喜欢把CATALINA_HOME和CATALINA_BASE配置到系统环境变量中去，我们不这么做，我们要做的只是把JDK及CLASSPATH配置到环境变量中去即可，因为这个可以通用。
CATALINA_HOME和CATALINA_BASE的区别。简单的说，CATALINA_HOME是Tomcat的安装目 录，CATALINA_BASE是Tomcat的工作目录。如果我们想要运行Tomcat的 多个实例，但是不想安装多个Tomcat软件副本。那么我们可以配置多个工作 目录，每个运行实例独占一个工作目录，但是共享同一个安装目录

下面讲具体的配置方法。

找到Tomcat的startup.sh文件，打开进行编辑。

在文件的开始位置，可以在一大堆注释的后面，加入
export CATALINA_BASE=/usr/ratest/apache-tomcat-7.0.16
export CATALINA_HOME=/usr/ratest/apache-tomcat-7.0.16

/usr/ratest/apache-tomcat-7.0.16这个就是tomcat的安装文件夹位置，不同的tomcat指定相应的文件夹即可。

注意，这两句话一定要在exec “$PRGDIR”/”$EXECUTABLE” start “$@”这句话的前面，我们放在文件的开始位置了，所以，就可以不考虑了。

然后就是要修改shutdown.sh文件，同样在头部加入上面的两行即可，也要在exec “$PRGDIR”/”$EXECUTABLE” stop “$@”的前面。

好了，解决了第一个问题，下面说第二个问题的解决方法。

找到并打开server.xml文件，里面有诸如8080，8009，8443等等端口配置，统一给这些数字加上100，或者1000或者其他什么数字，只要是不跟其他Tomcat或者当前linux上其他服务的端口重复即可。

现在进入Tomcat的bin文件夹，运行./startup.sh看看是不是可以启动多个了。

很多tomcat进程退出（或者进程假死），都是由于频繁的抛出OutOfMemeoryError导致的。

为了让tomcat退出前或者发生OutOfMemeoryError时自动dump堆栈信息，方便事后排查问题，我们可以做如下操作：

1、 在tomcat启动参数中加入两个参数 -XX:+HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=/export/home/tomcat/domains/server2/oom.hprof

2、 重启tomcat

参数说明
（1）-XX:+HeapDumpOnOutOfMemoryError 表示当JVM发生OOM时，自动生成DUMP文件。
（2）-XX:HeapDumpPath=存储文件/目录 表示生成DUMP文件的路径

想从JAVA转到obj-c，看了些基础的东西，感觉很奇怪，可能不太习惯，在网上看到一个不错文章有助理解obj-c的一些核心机制。

SomeClass.h
@interface SomeClass : NSObject{
}
-(void) print;
@end 

#import "SomeClass.h"
 
@interface SomeClass (Hello)
-(void)hello;
@end

#import "SomeClass+Hello.h"
@implementationSomeClass (Hello)
-(void)hello{
    NSLog (@"name：%@ ", @"Jacky");
}
@end 

#import "SomeClass+Hello.h"
 
SomeClass * sc =[[SomeClass alloc] init];
[sc hello] 

@protocol ProcessDataDelegate <NSObject>
@required
- (void) processSuccessful: (BOOL)success;

@optional
- (id) submitOrder: (NSNumber *) orderid;
@end

@interface TestAppDelegate : NSObject<ProcessDataDelegate>;

@end

@implementation TestAppDelegate

- (void) processSuccessful: (BOOL)success{
    if (success) {
        NSLog(@"成功");
    }else {
        NSLog(@"失败");
    }
}

@end 

@protocol A
     -(void)methodA;
@end
@protocol B <A>
     -(void)methodB;
@end

[obj conformsToProtocol:@protocol(ProcessDataDelegate)] 

首先在web工程src目录下新建一个database.properties 文件
内容如下：

user=root
password=root
databaseType=com.mysql.jdbc.Driver
url=jdbc:mysql://192.168.2.232:3306/oa? seUnicode=true&amp;characterEncoding=UTF8&amp;zeroDateTimeBehavior=convertToNull

 这里的内容随自己的合适而变化，这里不多说了；

在新建一个读取.properties文件新类：

package com.junhai.tamsys.util;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Properties;

public class DatabaseConfigure {
 private Properties property;
 private FileInputStream inputFile;
 private FileOutputStream outputFile;

 public DatabaseConfigure() {
  property = new Properties();
 }

 public DatabaseConfigure(String filePath) {
  property = new Properties();
  try {
   inputFile = new FileInputStream(filePath);
   property.load(inputFile);
   inputFile.close();
  } catch (FileNotFoundException e) {
   System.out.println("读取属性文件--->失败！- 原因：文件路径错误或者文件不存在");
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

 /*
  * 重载函数，得到key的值 @param key 取得其值的键 @return key的值
  */
 public String getValue(String key) {
  if (property.containsKey(key)) {
   return property.getProperty(key);

  } else
   return "";
 }

 /*
  * 重载函数，得到key的值
  *
  * @param fileName propertys文件的路径+文件名 @param key 取得其值的键 @return key的值
  */
 public String getValue(String fileName, String key) {
  try {
   String value = "";
   inputFile = new FileInputStream(fileName);
   property.load(inputFile);
   inputFile.close();
   if (property.containsKey(key)) {
    value = property.getProperty(key);
    return value;
   } else
    return value;
  } catch (FileNotFoundException e) {
   e.printStackTrace();
   return "";
  } catch (IOException e) {
   e.printStackTrace();
   return "";
  } catch (Exception ex) {
   ex.printStackTrace();
   return "";
  }
 }

 /*
  * 清除properties文件中所有的key和其值
  */
 public void clear() {
  property.clear();
 }

 /*
  * 改变或添加一个key的值，当key存在于properties文件中时该key的值被value所代替， 当key不存在时，该key的值是value
  * @param key 要存入的键 @param value 要存入的值
  */
 public void setValue(String key, String value) {
  property.setProperty(key, value);
 }

 /*
  * 将更改后的文件数据存入指定的文件中，该文件可以事先不存在。 @param fileName 文件路径+文件名称 @param
  * description 对该文件的描述
  */
 public void saveFile(String fileName, String description) {
  try {
   outputFile = new FileOutputStream(fileName);
   property.store(outputFile, description);
   outputFile.close();
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException ioe) {
   ioe.printStackTrace();
  }
 }

 public static void main(String[] args) {
  DatabaseConfigure test=new DatabaseConfigure("./src/database.properties");
  System.out.println(test.getValue("user"));
  System.out.println(test.getValue("databaseType")+";"+test.getValue("url"));
  
 }
}

Hiberante3 一级缓存总结

1．             Session 级别的缓存，它同session邦定。它的生命周期和session相同。Session消毁，它也同时消毁；管理一级缓存，一级缓存无法取消，用两个方法管理，clear(),evict()

2．             两个session 不能共享一级缓存，因它会伴随session的生命周期的创建和消毁；

3．             Session缓存是实体级别的缓存，就是只有在查询对象级别的时候才使用，如果

使用HQL和SQL是查询属性级别的，是不使用一级缓存的！切记！！！！

4 .  iterate 查询使用缓存，会发出查询Id的SQL和HQL语句，但不会发出查实体的，

它查询完会把相应的实体放到缓存里边，一些实体查询如果缓存里边有，就从缓存中查询，但还是会发出查询id的SQL和HQL语句。如果缓存中没有它会数据库中查询，然后将查询到的实体一个一个放到缓存中去，所以会有N+1问题出现。

5 . List()和iterate 查询区别：

使用iterate,list查询实体对象*N+1问题，在默认情况下，使用query.iterate查询，有可以能出现N+1问题

所谓的N+1是在查询的时候发出了N+1条sql语句1:首先发出一条查询对象id列表的sqlN:

根据id列表到缓存中查询，如果缓存中不存在与之匹配的数据，那么会根据id发出相应的sql语句list和iterate的区别？

list每次都会发出sql语句，list会向缓存中放入数据，而不利用缓存中的数据

iterate：在默认情况下iterate利用缓存数据，但如果缓存中不存在数据有可以能出现N+1问题

6．Get()和load(),iterate方法都会使用一级缓存，

7.hiberate3 session 存储过程如下：

       例如 object 对象

       Session.save(object);

       这时候不会把数据放到数据库，会先放到session缓存中去，数据库中没有相应记录，session.flush();才发SQL和HQL语句，数据库中有了相应记录，

       但是数据库用select查不到，这是跟数据库事物级别有关系，（这里在说下数据库的事务隔离级别一共四种如下：）
    数据库隔离级别：
        隔离级别                       是否存在脏读  是否存在不可重复读     是否存在幻读；
    Read UnCommited(未提交读)               Y            Y                     Y
    Read Commited (提交读 oraclel默认)      N            Y                     Y
    Repeatable Read(不可重复读（Msql默认）)  N            N                     Y 
    Serializable(使用很少)                  N            N                     N
    

       Session.beginTrransaction().commit();

       事物提交后可以查询到了。

Session.flush()语句但是为什么不写呢，因为commit()会默认调用flush();

Hiberante3 二级缓存总结

1．Hibernate3的（sessionFactory）二级缓存和session级别的缓存一样都只对实体对象做缓存，不对属性级别的查询做缓存；二级缓存的生命周期和sessionFactory的生命周期是一样的，sessionFactory可以管理二级缓存；

2．sessionFactory级别的缓存，需要手动配置；所有的session可以共享sessionFactory 级别的缓存；（一般把一些不经常变化的实体对象放到sessionFactory级别的缓存中，适合放不经常变化的实体对象。）

3．Hiberante3二级缓存的配置和使用方法如下：

1． 必须把ehcache.jar包导入，然后到Hibernate3.2的etc文件下把ehcache.xml复制到工程src目录下（ehcache.xml里边的参数里边有详细英文说明）；

（说明：ehcache.jar是第三方法的缓存产品，hiberante只是把它做了集成，还有好多第三方hibernate集成的缓存产品，相关说明请查阅hiberante3开发手册；ehcache支持分布应用的（这个和Hibernate3.2开发手册有出入，经过官网查证确实支持了），如果有分布式需求，请换成支持分布式的二级缓存产品，hiberate3开发手册都有相头说明。配置方法都类似）；

4．Hibernate3的二级缓存默认是开起的，也可以指定开起。在hibernate.cfg.xml 文件下配置如下：

*修改hibernate.cfg.xml文件，开户二级缓存；

                     <property name=”hibernate.cache.use_second_level_cache”>true</property>

                     *指定二级缓存产品的提供商；

<property name=”hibernate.cache.provider_class”> org.hibernate.cache.EhCacheProvider

</property>

要让那些实体使用二级缓存，在hibernate.cfg.xml配置文件中加入：

<!—

让这个实体用二级缓存 也可以在实体中映射文件去配置即：

<cache usage="read-only"/>

-->

<class-cache class=”com.zzz.hibernate.ClassT” usage=”read-only”/>

Read-only一般使用这个策略，其它的hibernate3开发手册中也有详细介绍；

CacheMode去hibernate3开发手册中搜索这个关键字，可以找到一级缓存和二级缓存交互使用的问题；

<?xml version="1.0" encoding="UTF-8"?>
<web-app version="2.5" xmlns="http://java.sun.com/xml/ns/javaee"
 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
 xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
 http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd">

 <!-- 配置spring监听器和上下文变量 -->
 <context-param>
  <param-name>contextConfigLocation</param-name>
  <param-value>/WEB-INF/applicationContext-*.xml</param-value>
 </context-param>

 <listener>
  <listener-class>
   org.springframework.web.context.ContextLoaderListener
  </listener-class>
 </listener>
 <!-- spring end -->

<!-- 配置字符过滤器-->
 <filter>
  <filter-name>encodingFilter</filter-name>
  <filter-class>
   org.springframework.web.filter.CharacterEncodingFilter
  </filter-class>
  <init-param>
   <param-name>encoding</param-name>
   <param-value>GBK</param-value>
  </init-param>
 </filter>
 <filter-mapping>
  <filter-name>encodingFilter</filter-name>
  <url-pattern>/*</url-pattern>
 </filter-mapping>

 <!--让spring来过滤管理Hiberante中的session-->
 <filter>
  <filter-name>lazyLoadingFilter</filter-name>
  <filter-class>
   org.springframework.orm.hibernate3.support.OpenSessionInViewFilter
  </filter-class>
 </filter>

 <!-- spring end -->

 <!-- 增加struts2所需要的过滤器,以便在服务器启动时,拦截URL请求 -->
 <filter>
  <filter-name>struts2</filter-name>
  <filter-class>
   org.apache.struts2.dispatcher.FilterDispatcher
  </filter-class>
 </filter>

 <filter-mapping>
  <filter-name>lazyLoadingFilter</filter-name>
  <url-pattern>*.action</url-pattern>
 </filter-mapping>

 <filter-mapping>
  <filter-name>struts2</filter-name>
  <url-pattern>/*</url-pattern>
 </filter-mapping>
  </web-app>