阅读全文……

发表评论

IT瘾于2014年6月30日 下午05时58分00秒发布 #

阅读全文……

发表评论

IT瘾于2014年6月30日 上午01时32分00秒发布 #

LVS+Keepalived 实现高可用的前端负载均衡器

 

一、前言

       这篇文章是前几篇文章的总结，我们先简单的总结一下我们前面讲解的内容，前面我们讲解了，LVS（负载均衡器）、Heartbeat、Corosync、Pacemaker、Web高可用集群、MySQL高可用集群、DRDB、iscsi、gfs2、cLVM等，唯一没有讲解的就是LVS可用，也就是前端高可用，我们这一篇博文主要讲解内容。在说这个之前我们得和大家讨论一个问题，也是好多博友问的问题。Heartbeat、Corosync、Keepalived这三个集群组件我们到底选哪个好，首先我想说明的是，Heartbeat、Corosync是属于同一类型，Keepalived与Heartbeat、Corosync，根本不是同一类型的。Keepalived使用的vrrp协议方式，虚拟路由冗余协议 (Virtual Router Redundancy Protocol，简称VRRP)；Heartbeat或Corosync是基于主机或网络服务的高可用方式；简单的说就是，Keepalived的目的是模拟路由器的高可用，Heartbeat或Corosync的目的是实现Service的高可用。所以一般Keepalived是实现前端高可用，常用的前端高可用的组合有，就是我们常见的LVS+Keepalived、Nginx+Keepalived、HAproxy+Keepalived。而Heartbeat或Corosync是实现服务的高可用，常见的组合有Heartbeat v3(Corosync)+Pacemaker+NFS+Httpd 实现Web服务器的高可用、Heartbeat v3(Corosync)+Pacemaker+NFS+MySQL 实现MySQL服务器的高可用。总结一下，Keepalived中实现轻量级的高可用，一般用于前端高可用，且不需要共享存储，一般常用于两个节点的高可用。而Heartbeat(或Corosync)一般用于服务的高可用，且需要共享存储，一般用于多节点的高可用。这个问题我们说明白了，又有博友会问了，那heartbaet与corosync我们又应该选择哪个好啊，我想说我们一般用corosync，因为corosync的运行机制更优于heartbeat，就连从heartbeat分离出来的pacemaker都说在以后的开发当中更倾向于corosync，所以现在corosync+pacemaker是最佳组合。但说实话我对于软件没有任何倾向性，所以我把所有的集群软件都和大家说了一下，我认为不管什么软件，只要它能存活下来都有它的特点和应用领域，只有把特定的软件放在特定的位置才能发挥最大的作用，那首先我们得对这个软件有所有了解

阅读全文……

发表评论

IT瘾于2014年6月27日 上午12时31分00秒发布 #

几种磁盘阵列技术

    RAID技术是一种工业标准，各厂商对RAID级别的定义也不尽相同。目前对RAID级别的定义可以获得业界广泛认同的有4种，RAID 0、RAID 1、RAID 0＋1和RAID 5。

    RAID 0是无数据冗余的存储空间条带化，具有成本低、读写性能极高、存储空间利用率高等特点，适用于音、视频信号存储、临时文件的转储等对速度要求极其严格的特殊应用。但由于没有数据冗余，其安全性大大降低，构成阵列的任何一块硬盘的损坏都将带来灾难性的数据损失。这种方式其实没有冗余功能，没有安全保护，只是提高了磁盘读写性能和整个服务器的磁盘容量。一般只适用磁盘数较少、磁盘容易比较紧缺的应用环境中，如果在RAID 0中配置4块以上的硬盘，对于一般应用来说是不明智的。

    RAID 1是两块硬盘数据完全镜像，安全性好，技术简单，管理方便，读写性能均好。因为它是一一对应的，所以它无法单块硬盘扩展，要扩展，必须同时对镜像的双方进行同容量的扩展。因为这种冗余方式为了安全起见，实际上只利用了一半的磁盘容量，数据空间浪费大。

    RAID 0＋1综合了RAID 0和RAID 1的特点，独立磁盘配置成RAID 0，两套完整的RAID 0互相镜像。它的读写性能出色，安全性高，但构建阵列的成本投入大，数据空间利用率低。

    RAID 5是目前应用最广泛的RAID技术。各块独立硬盘进行条带化分割，相同的条带区进行奇偶校验（异或运算），校验数据平均分布在每块硬盘上。以n块硬盘构建的RAID 5阵列可以有n－1块硬盘的容量，存储空间利用率非常高。任何一块硬盘上的数据丢失，均可以通过校验数据推算出来。它和RAID 3最大的区别在于校验数据是否平均分布到各块硬盘上。RAID 5具有数据安全、读写速度快，空间利用率高等优点，应用非常广泛，但不足之处是如果1块硬盘出现故障以后，整个系统的性能将大大降低。

    RAID 1、RAID 0＋1、RAID 5阵列配合热插拔（也称热可替换）技术，可以实现数据的在线恢复，即当RAID阵列中的任何一块硬盘损坏时，不需要用户关机或停止应用服务，就可以更换故障硬盘，修复系统，恢复数据，对实现高可用系统具有重要的意义。 

阅读全文……

发表评论

IT瘾于2014年6月27日 上午12时09分00秒发布 #

FC-SAN和IP-SAN两者的优缺点分别是什么？
一般来说，企业在面临iSCSI SAN存储解决方案时，多半喜欢拿FC SAN及NAS与其做一番比较。在此先就FC与iSCSI做一比较，基本两者同属走Block协议的SAN架构，只不过前者透过光纤，后者藉由IP传输数据罢了，而两者在管理及应用上也大同小异，其间只不过优劣好坏的差异。
至于SAN与NAS的差异而言，笔者走访了许多iSCSI厂商，大部分厂商对于此比较，多半都面露疑惑不解的表情，他们认为SAN与NAS是完全不同架构的存储方案，前者支持Block协议，后者则支持File协议，所以拿两个完全不同协议及架构的标准相比，是不太适宜的。
如果硬要从中做个区别的话，精业公司产品技术处存储产品整合服务部产品经理邱显进倒提出了一个简显易懂的区别方法，那就是SAN的精髓在于分享存储配备（Sharing Storages）；NAS则在于分享数据（Sharing Data）。总而言之，NAS与SAN因为架构及应用领域的不同，所以不会相互取代，而会共存于企业存储网络之中。
不论如何，为了让读者进一步了解iSCSI、FC及NAS的差异，在此还是尽量做一番归纳整理，以供读者参考：

接口技术：iSCSI和NAS一样透过IP网络来传输数据，FC则不一样，数据是透过光纤 通道（Fibre Channel）来传递。

数据传输方式：同为SAN的iSCSI及FC都采用Block协议方式，而NAS则采用File协议。

传输速度：就目前的传输速度而言是FC（2Gb）最快、iSCSI（1Gb）次之，NAS居末。基本上，FC及iSCSI的Block Protocol会比NAS的File Protocol来得快，这是因为在操作系统的管理上，前者是一个“本地磁盘”，后者则会以“网络磁盘”的名义显
示。所以在大量数据的传输上，iSCSI 绝对会比NAS快得多。

资源共享：iSCSI和NAS共享的是 存储资源，NAS共享的是数据。
管理门坎：iSCSI和NAS都采用IP网络的现有成熟架构。所以可延用既有成熟的网络管理机制，不论是建置、管理或维护上，都非常方便及容易。而FC则完全独立于一般网络系统架构，所以需由FC供货商分别提供专属管理工具软件。

管理架构：透过网络交换机，iSCSI及FC可有效集中控管多台主机对 存储资源的存取及利用，善用资源的调配及分享，同时速度上也快于网络磁盘的NAS。

成本：比起FC而言，以太网络是个十分成熟的架构，而熟悉的人才甚多，所以同样采用IP网络架构的iSCSI及NAS，建置成本低廉、管理容易而维护方便。至于与FC在建置成本上的进一步比较。

传输距离：原则上，三者都支持长距离的数据传输。FC的理论值可达100公里。透过IP网络的NAS及iSCSI理论上都没有距离上的限制，但NAS适合长距小档案的传输，iSCSI则可以进行长距大量资料的传递。

系统支持：相较起来，iSCSI仍然比较少。FC主要是由适配卡供货商提供驱动程序和简单的管理程序。

iSCSI与各类型存储方案综合评比 
与Fiber Channel（以下简称FC）一样，iSCSI也属于SAN大家庭中的一员，它的问世显然是冲着FC SAN的缺点而来的。长久以来，FC几乎成了SAN的代名词，但由于相关软硬件的建置成本偏高、管理技术及门坎也较高，所以几乎只有中大型企业才有能力做这方面的建置与规划，中小企业限于自身规模，也只有望洋兴叹、徒呼负负的份。

无传输距离限制、建置管理成本低是最大特点
iSCSI最重要的就是能在成本上提出大幅改善的方案，也因此打破了SAN为中大型企业禁脔的藩篱，让中小企业也能享受到SAN所带来的好处及便利。到底是哪些优良特质，让iSCSI成为目前存储业界最热门的话题呢？以下即为读者做一番简赅的归纳及分析：
建置成本低廉：不论是适配卡、 交换机或缆线的建置，iSCSI都比FC便宜许多。其中适配卡部分，只要Host端主机本身内建的一般网络卡或网络芯片，搭配免费下载的iSCSI Initiator驱动程序即可，所以在适配卡方面可以达到完全免费的境界。
管理门坎及维护成本更低：一般来说，FC SAN多半需要特定的工具软件来操作管理，所以需要对人员进行一定时间的教育训练，而且费用不低。但由于iSCSI乃透过IP网络来传输数据及分配 存储资源，所以只要使用网络现有的管理功能即可，相较起来，的确可以省下大笔管理人力及训练成本。
节省存储资源、做好集中管理：由于iSCSI与FC同样支持区块协议（Block Protocol）的数据存取模式，所以比采用档案协议（File Protocol）的NAS，更能透过集中管理的方式，有效避免存储资源的浪费，进而节省不必要支出。
没有距离的限制：由于iSCSI是透过无远弗届的IP网络来传输数据，所以理论上，传输距离也可达到无限制的境界，这对于异地数据的传输及备援等应用相当有帮助。
传输速度够快：拜GbE以太网络之赐，理论上，iSCSI的速度可达1Gb，虽然速度仍比不上FC SAN的2Gb，但效能上已超越大部分的NAS。更重要的是，一旦下世代的10Gb以太网络普及的时候，iSCSI就可能以10Gb的高速狂飙，甚至比FC SAN的下世代版本－4Gb还要快。
人才较多：随着因特网的日益兴盛，造就了取之不尽、用之不竭的TCP/IP网络人才，比起门坎较高的FC SAN来说，这对于专走IP网络Base的iSCSI而言，可说是一大利多。
数据碰撞及支持性低等问题成为推展阻力
天底下没有十全十美的事物，虽然iSCSI的优点不少，而且十分抢眼，但仍有许多待解决的缺点，以下就让我们一起分析看看iSCSI到底有哪些缺陷：
1. 扰人的噪声碰撞问题：由于iSCSI走的是IP网络，其中当然充斥着来自全球各地的庞大数据及噪声，所以碰撞情形也就在所难免了，如此一来，在数据传输的过程中，就很容易导致延迟的情形发生，大大影响了传输的效能，甚至数据的正确性。针对这类问题，不少厂商专研解决之道，其中像是乔鼎信息（Promise）即宣称，该产品提供的Data Digest功能，可有效解决噪声问题。
2. 仍有改进空间的效能瓶颈：这方面可分成下列几项来讨论。
(1) 传输频宽问题：前文已提到，目前的1Gb频宽，尚不及FC的2Gb，这方面待要等到10Gb以太网络普及之后，才有可能赶上。但就目前企业的网络状况来看，GbE以太网络的普及率都有待加强了，所以10Gb何时来临，还是未定之数。
(2) 流量控制问题：这方面也没有FC来得好。
(3) I/O端的速度限制：Brocade指出在Host主机及Target存储设备两处的I/O端速度一直提振不上来，所以即使10Gb以太网络真的普及，I/O端的速度瓶颈仍然会拖跨这个传输效能。
(4) 软件iSCSI Initiator效能不彰：其乃透过软件仿真来执行SCSI指令，所以会耗费掉大量的CPU资源，造成整体效能的低落。这个问题虽然可以透过安装频率较高的CPU来解决，但相对地便会有额外的成本支出。
3. 硬件iSCSI适配卡较贵：如果想要让整体效能有好的表现，那么就必须添置较贵的iSCSI HBA卡或稍贵的TOE HBA卡（TCP Offload Engine），整体成本会因而大幅攀升。据Brocade指出，不论是FC HBA卡或FC交换机的价格都在逐步调降中，同时该公司会推出价格颇为低廉的FC交换机，如此一来，在寻求高效能的前提下，iSCSI的成本优势会相对减少。
4. 支援的平台及软硬件仍少：虽然目前Windows、Linux、UNIX、Netware都已陆续推出软硬件的Initiator，但数量及完备性仍不足，尤其是版本特多的Linux，目前只有SuSE及Redhat有解决方案；其中，SuSE只有软件、Redhat只有硬件。此外，HP-UX及Novell Netware只有软件，SUN Solaris则只有硬件，而且一些平台上的设定十分复杂困难。换句话说，目前只有微软Windows平台具备最完备的支持性。但是目前业界及政府机构的数据中心，有相当数量是采用非Windows平台系统，再加上也有不少公司内部系统是属于多种作业平台环境，所以各平台解决方案的提出，仍是iSCSI急待解决的重要课题。
5. 令人质疑的安全性：IP网络环境复杂，再加上懂IP的人相对的多，所以安全性也相对地令人质疑。
6. 无法兼顾效能及跨平台性：前面已提到iSCSI Initiator可分为三种，亦即软件Initiator驱动程序、硬件的TOE HBA卡及iSCSI HBA卡。就效能而言，Initiator驱动程序最差、TOE居中、iSCSI HBA卡最佳。但是iSCSI HBA只能走iSCSI协议，而无法透过NFS（Network File System，SUN制定）或CIFS（Common Internet File System，微软制定）等档案系统协议与应用服务器沟通。但Initiator驱动程序及TOE则同时支持iSCSI、NFS及CIFS三种协议

阅读全文……

发表评论

IT瘾于2014年6月26日 下午06时40分00秒发布 #

阅读全文……

发表评论

IT瘾于2014年6月26日 下午06时30分00秒发布 #

当虚拟化需要借助共享存储时，IT经理们应该决定采用块级FC和iSCSI存储，还是文件级的NFS存储？iSCSI和NFS之间的差异已经成为IT经理们部署服务器虚拟化时不得不面对的问题之一。

根据存储专家Nigel Poulton的说法，尽管成本高于NFS，大多数的VMware仍是基于FC和iSCSI技术部署的。块级存储提供的高性能和高可靠性已经得到事实证明，尤其在关键的生产环境内。

同时也不乏一些重量级专家，如Scott Lowe，强烈建议NFS存储。理由是它的易管理、大数据存储以及NFS阵列具备的一些诸如重复数据删除等可以节省成本的技术。

参考如下的iSCSI vs. NFS内容可以帮助您决定采用块级FC或iSCSI共享存储，还是基于以太网的NFS阵列。

块级存储的性能和可靠性高于NFS存储

Nigel Poulton，撰稿人

您的VMware环境应该选择块级还是文件级存储？

这样的问题不会有完美的答案。多数情况下，解决方案可以根据如下的准则产生：如果您计划把VMware用于实际工作环境，答案是块级；如果只是打算测试一下，答案是文件级。下面是理由：

实际工作 vs.测试

实际工作主要指那些常见的：生产、核心系统、高可用、在线交易、高性能、关键业务、数据中心、无停顿、零停机等情况。

另一方面，测试包括了任何非上述情况的应用。例如，可能会包括家庭网络、实验室、测试和开发环境等成本至上的应用。

性能和可靠性

块级存储通常有专用的高速数据传输网络，保证它的高性能和高可靠性。专用网络指的是主动预防、少争用、高带宽的网络。更少的网络争用降低了其它网络发生故障而受到波及的情况。

协议卸载能力也是增加性能的方式之一。FC和iSCSI HBA都提供协议卸载能力。这些HBA对协议相关功能的处理要比主CPU更快，更重要的是可以释放CPU资源用于其它的ESX任务。

还有一点要注意的是，VMware对vSphere 4.0 投入大量精力在改善和优化iSCSI initiator软件性能上，相比3.5版本性能会有大幅增强。

支持者

抛开纯技术性优越不谈，公平地讲之前大多数生产环境VMware部署都是基于块级存储——尤其是FC存储。即使听到反对声音时，这种现状会让我们对在实际工作环境采用块级存储感到放心一些。

为证实该观点，我最近联系一些已经使用和部署VMware的朋友和同行，并询问他们的使用情况。很有趣的结果是，当前他们几乎在绝大多数情况下都基于块级存储部署VMware。

在个人主页上我也设置了一个快速投票活动针对同一主题。截止1月5号，投票结果中72%选择了块级存储，文件级存储仅占10%，剩下的选择了两者的混合环境选项。

从中可以看到尽管块级存储方案通常比文件级要贵得多，更为成熟地，被用户广泛接受和信任的解决方案依然毫无疑问是块级存储。所以，如果您计划通过VMware进行实际工作，而且对性能、可靠性有要求，让人放心的做法就是选择块级存储。不要轻易被文件级存储所宣传的那些优势煽动，或许您永远都享受不到。

使用NFS作为虚拟机存储的六个原因

Scott Lowe

如下六个方面是我们选择用NFS存储代替传统块级存储作为虚拟机存储设备的理由。

1.简单地操作模式。和传统块级存储相比，NFS的可操作性要好得多。调整LUN大小是很复杂的事情，需要同时涉及LUN和VMFS（Virtual Machine File System）存储大小的调整。调整NFS文件系统要相对简单一些。vSphere最新提供的VMFS扩展功能可以有所帮助，但也要比NFS麻烦很多。另外，用NFS代替块级存储后，使用重复数据删除功能（多数阵列支持这一功能）也要更加简单和便捷。

2.大数据存储。VMFS LUN受限于2TB大小，NFS则不会——某些阵列LUN可达16TB大小。

3.基于以太网的架构。NFS使用现有的以太网架构。另一方面，iSCSI也可以，所以这方面两种协议处于平手。

4.基于文件系统上的高级功能。NFS相比传统的块级设备可以提供更多高级功能，因为存储阵列拥有对文件系统的控制权。在NFS阵列中，诸如快照和克隆这样的技术可以得到更为广泛的支持。例如，在Sun Storage 7000或NetApp FAS阵列中都提供了接近实时的快照和保留空间的克隆功能。

5.开放的访问方式。VMware设计VMFS完全是为支持虚拟环境的，不过这也导致VMFS几乎成为VMware环境专用。也就意味着对VMFS数据的访问会比较困难。而NFS天生就是一种跨平台协议，使得备份、复制或其它任务对虚拟机的访问变得简单。

6.光明的未来。NFS的未来很大程度要看pNFS（parallel NFS）的发展,它为scale-out存储、包括多存储控制器（NAS机头）和多个卷的平台提供了一种标准。pNFS希望可以对多种工作负载（也包括虚拟化）提供增强的性能表现。(李哲贤/译)

阅读全文……

发表评论

IT瘾于2014年6月26日 下午06时09分00秒发布 #

    如果主服务器宕机，造成的损失是不可估量的。要保证主服务器不间断服务，就需要对服务器实现冗余。在众多的实现服务器冗余的解决方案 中，heartbeat为我们提供了廉价的、可伸缩的高可用集群方案。我们通过heartbeat+drbd在Linux下创建一个高可用(HA)的集群 服务器。

阅读全文……

发表评论

IT瘾于2014年6月26日 上午01时18分00秒发布 #

4 Windows下 NFS 客户端的安装及设置

在Windows上使用NFS客户端，需要把nfs共享目录映射到一个驱动器。此处假定为映射的驱动器为N:，而nfs共享目录为192.168.6.55:/vmsnfs。

4.1 安装Microsoft Windows Services for UNIX

Windows Services for UNIX 3.5 提 供支援充分和整合完全的跨平台網路服務，適應需要 Windows 和 UNIX 基礎環境之間交互操作性的企業客 戶。 Windows Services for UNIX 3.5 為企業客戶提供儲存在多個平台的資訊之緊密存取，統一了跨平台的網路管理，並且重複 使用 UNIX 應用程式和 Windows 上的指令碼。其中包括支援網路檔案系統 (NFS)。

下载Microsoft Windows Services for UNIX

地址： http://www.microsoft.com/taiwan/windows/sfu/

安装程序： SFU35SEL_EN.exe  217 MB (228,178,504 字节)

安装Microsoft Windows Services for UNIX

注意与NFS有关的两个组件是一定要安装的

NFS->Client for NFS 
Authentication tools for NFS->Server for PCNFS

安装过程比较简单，此处略过。

4.2 在Windows下配置NFS客户端

打开Services for UNIX Administration配置用户名

点 “开始菜单”->“所有程 序”->“Windows Services for UNIX”->“Services for UNIX Administration”, 会弹出一个名为“Services for UNIX Administration”的窗口。

左边栏切到Server for PCNFS。

右边栏切到Groups，添加Group Name为root，Group ID(GID)为0的组。

右边栏切到Users，添加User name为root，User logon name为root，Primary group name为root，User ID(UID)为0的用户，密码不必与Linux系统的密码相同。

点击右上角的Apply保存。

映射网络驱动器到NFS共享目录（界面操作方式，不推荐）

在“网上邻居”上按右键，选择“映射网络驱动器”，会弹出映射网络驱动器对话框。

选择盘符，比如N:

输入网络资源路径：192.168.6.55:/vmsnfs

点 “确定”。会弹出一个NFS login successful的信息框，注意检查显示的UID和GID的值（一般为-2），点“否”，会弹出 Client for NFS Drive N:对话框。选中Login using PCNFS authentication对话框，在 Server name中填入localhost，在User name中填入root，在Password中填入前面设定的密码，点“确定”，会再次弹 出NFS login successful的信息框，此次会显示UID和GID均为0，点“确定”。

这时打开“我的电脑”，会看到增加了一个盘符N:。在其上按右键打开属性对话框，切换到NFS Attributes页，会看到权限，切换到NFS Mount Options，会看到UID和GID等信息。注意确认一下UID和GID一定要为0。

映射网络驱动器到NFS共享目录（批处理脚本方式，推荐）

上 面这段挺费劲的，但我不推荐使用这种方式来设置，因为一旦重新启动机器，你再打开“我的电脑”，在NFS对应的盘符N:属性就会看到UID和GID由还原 成了-2。还得先把它断开，然后重新设置，挺麻烦的。所幸微软提供了类似Unix下的命令行工具mount.exe，可以编写如下内容的批处理脚本并保存 为nfs.bat。其中第一行是用来记录操作日志的，第二行启动Server for PCNFS，第三行是避免mount命令出错，第四行是把nfs共 享目录挂载到N:（注意-p:xxx要设置成前面设定的密码），第五行列出N:下的文件和目录。

批处理代码  

1. echo mount nfs at %date% %time% >>c:\nfs.log  
2. net start pcnfsd >>c:\nfs.log  
3. net use /pers:no >>c:\nfs.log  
4. mount -o mtype=hard -o pcnfs=localhost -u:root -p:xxx 192.168.6.55:/vmsnfs N: >>c:\nfs.log  
5. dir N: >>c:\nfs.log   

双击执行nfs.bat，然后打开“我的电脑”就可以看到N:了，然后打开c:\nfs.log看一下。

Text代码  

1. mount nfs at 2010-11-19 星期五 11:33:39.15   
2. 命令成功完成。  
3.   
4. N: is now successfully connected to 192.168.6.55:/vmsnfs  
5.   
6. The command completed successfully.  
7. mounted    

如果看到successully之类的关键字眼，就表明mount成功了。

4.3 在Windows下使用NFS客户端会碰到的问题

Q：在挂载nfs共享目录时，mount.exe报1326错误，是什么原因？

Network Error - 1326

Type 'NET HELPMSG 1326' for more information.

A：根据提示，使用net helpmsg看一下，如下所示：

C:\>net helpmsg 1326

登录失败: 未知的用户名或错误密码。

这时，需要检查一下mount命令后面的-u:user和-p:password这两部分是否正确了。

Q：在挂载nfs共享目录时，mount.exe报85错误，是什么原因？

Network Error - 85

Type 'NET HELPMSG 85' for more information.

A：根据提示，使用net helpmsg看一下，如下所示：

C:\>net helpmsg 85

本地设备名已在使用中。

这是由于对同一个驱动器重复执行mount命令造成的，确认驱动器选择是否正确。

Q：创建目录或文件时报“拒绝访问”，怎么办？

A：首先打开“我的电脑”，在NFS映射的驱动器上按右键，打开属性对话框。切换到NFS Mount Options页，看显示的UID和GID是否为0，可能你看到的是-2。关闭属性对话框之后，在驱动器上按右键，选择“断开”，然后参照上一节重新设置。

如果看到NFS Mount Options页显示的UID和GID都为0，那么就要到NFS服务端去查找原因了。比如，检查一下共享目录的属主和组是否为nfsnobody，参见前面的章节。

Q：怎样做到登录Windows之后自动启动NFS？

A：按照4.2创建nfs.bat脚本，然后复制到“启动”目录（我的XP系统是“C:\Documents and Settings\Administrator\「开始」菜单\程序\启动”目录）。在登录之后就会自动挂载nfs共享目录。如果需要确认是否成功，打开c:\nfs.log看一下。

Q：怎样做到启动Windows之后自动挂载NFS，而不管是否登录？

A：这个就有点难了。本人试验了如下两种方式，都无法成功的挂在nfs共享目录。（奇怪，手工直接执行nfs.bat就能成功）

（1）安装Windows Resource Kits，里面有instsrv.exe和srvany.exe两个程序，制作了系统服务MountNFS，用来执行nfs.bat脚本。

（2）设置“任务计划”，执行文件为nfs.bat，触发条件为“计算机启动时”。

最后，只能将XP系统设置为自动登录才得以解决，不算很完美。具体如下：

先按照上一个问题中所述，将nfs.bat复制到“启动”目录。

然后执行“rundll32 netplwiz.dll,UsersRunDll ”,在弹出的用户账户对话框中，把“要使用本机，用户必须输入用户名和密码(E)”前面的钩去掉，然后点“确定”。这时，会提示输入账号和密码，输入好之后保存就行了。下次启动机器就会直接登录，而无需手工输入账号和密码了。

因为自动登录Windows之后会自动去执行“启动”目录的nfs.bat脚本，也就会挂载nfs共享目录了。

Q：怎样才能在Windows下用程序访问文件服务器上的文件？

A：在Linux下文件/vmsnfs/subdir/file.wav，可以直接访问，在Windows下在路径前面加上N:无法访问N:/vmsnfs/subdir/file.wav，必须要把路径里面的vmsnfs去掉，变成N:/subdir/file.wav才能访问。这样程序处理起来稍微有点麻烦。

如果在Linux文件服务器的共享目录上创建一个名为vmsnfs符号链接，就可以用N:/vmsnfs/subdir/file.wav来访问了，具体做法如下：

cd /vmsnfs

ln -s . vmsnfs

阅读全文……

发表评论

IT瘾于2014年6月26日 上午12时56分00秒发布 #

Gmail 邮件发送配置

 

email.properties 文件：

# Gmail Configuration
email.host=smtp.gmail.com 
email.port=587 
email.username=******
email.password=******
email.defaultEncoding=UTF-8

 

applicationContext.xml 文件：

    <!-- Email Service -->
    <bean id="mailSender" class="org.springframework.mail.javamail.JavaMailSenderImpl">
        <property name="host" value="${email.host}"/>
        <property name="port" value="${email.port}"/>
        <property name="username" value="${email.username}"/>
        <property name="password" value="${email.password}"/>
        <property name="javaMailProperties">
            <props>
                <prop key="mail.transport.protocol">smtp</prop>
                <prop key="mail.smtp.starttls.enable">true</prop>
        <prop key="mail.smtp.host">smtp.gmail.com</prop>
        <prop key="mail.smtp.auth">true</prop>
        <prop key="mail.smtp.port">465 </prop>
            </props>
            <!--
            <value>
                mail.smtp.auth=true
            </value>
             -->
        </property>
        <property name="defaultEncoding" value="${email.defaultEncoding}"></property>
    </bean>
    <bean id="emailSender" class="com.tucue.common.util.SimpleEmailSender">
        <property name="mailSender" ref="mailSender"></property>
    </bean>
    <!-- end of Email Service -->

 

FAQ ：

com .sun .mail .smtp .SMTPSendFailedException: 530   5 .7 . 0  Must  issue  a  STARTTLS  command  first .

 

A ：

<prop key="mail.smtp.starttls.enable">true</prop>

 

Send Batch Mail

http://static.springsource.org/spring/docs/2.5.x/api/org/springframework/mail/MailSender .html

 

Method Summary

void	send (SimpleMailMessage  simpleMessage)            Send the given simple mail message.
void	send (SimpleMailMessage [] simpleMessages)            Send the given array of simple mail messages in batch.

 

http://static.springsource.org/spring/docs/2.5.x/api/org/springframework/mail/javamail/JavaMailSender .html

 

Method Summary

MimeMessage	createMimeMessage ()            Create a new JavaMail MimeMessage for the underlying JavaMail Session of this sender.
MimeMessage	createMimeMessage (InputStream  contentStream)            Create a new JavaMail MimeMessage for the underlying JavaMail Session of this sender, using the given input stream as the message source.
void	send (MimeMessage  mimeMessage)            Send the given JavaMail MIME message .
void	send (MimeMessage [] mimeMessages)            Send the given array of JavaMail MIME messages in batch .
void	send (MimeMessagePreparator  mimeMessagePreparator)            Send the JavaMail MIME message prepared by the given MimeMessagePreparator.
void	send (MimeMessagePreparator [] mimeMessagePreparators)            Send the JavaMail MIME messages prepared by the given MimeMessagePreparators.

 

方案一：首先获取要发送邮件的所有地址，然后迭代的封装单个 MimeMessage 之后就将其发送出去（即发送一封邮件）。

 

SimpleEmailSender.java 文件

Java代码  

1.     /** 
2.      * 功能: 传入邮件接收者地址、标题和内容，然后发送单个邮件服务 
3.      * @param {@link String} emailAddress 
4.      * @param {@link String} subject 
5.      * @param {@link String} content 
6.      * @throws MessagingException 
7.      */  
8.     public static void sendSimpleEmail(<span style="color: #ff0000;">String receiver</span>  
9. , String subject, String content) throws MessagingException {  
10.         JavaMailSender sender = (JavaMailSender) mailSender;  
11.           
12.         <span style="color: #ff0000;">MimeMessage mimeMessage</span>  
13.  = sender.createMimeMessage();  
14.         MimeMessageHelper messageHelper = new MimeMessageHelper(mimeMessage, true, "UTF-8");  
15.         messageHelper.setFrom("***@<span style="color: #ff0000;">gmail</span>  
16. .com");  
17.         messageHelper.setTo(receiver);  
18.         messageHelper.setSubject(subject);  
19.         messageHelper.setText(content, true);  
20.           
21.         sender.send(<span style="color: #ff0000;">mimeMessage</span>  
22. );  
23.     }  

 

 UserInfoAction.java 文件

Java代码  

1.     // 用户 -> 批量邮件发送  
2.     public String sendBatchEmail() {  
3.         if(!emailReceiverList.equals("")) { // 发送用户邮件  
4. //          String[] receiverList = emailReceiverList.split(",");  
5.             String[] receiverList = new String[20];  
6.             for(int i = 0; i < 20; ++i) {  
7.                 receiverList[i] = "[email protected]";  
8.             }  
9.             long start = System.currentTimeMillis();  
10.             for(<span style="color: #ff0000;">String receiver: receiverList</span>  
11. ) {  
12.                 try {  
13.                     <span style="color: #ff0000;">SimpleEmailSender.sendSimpleEmail(receiver, emailSubject, emailContent);</span>  
14.   
15.                 } catch (MessagingException e) {  
16.                     e.printStackTrace();  
17.                 }  
18.             }  
19.             long end = System.currentTimeMillis();  
20.             System.out.println(end - start);  
21.         } else {// 发送用户组邮件  
22.             List<String> receiverList = userInfoService.getUserEmailByGroupId(groupID);  
23.             for(String receiver: receiverList) {  
24.                 try {  
25.                     SimpleEmailSender.sendSimpleEmail(receiver, emailSubject, emailContent);  
26.                 } catch (MessagingException e) {  
27.                     e.printStackTrace();  
28.                 }  
29.             }  
30.         }  
31.   
32.         return SUCCESS;  
33.     }  

 方案二：首先获取要发送邮件的所有地址，然后一起封装成 MimeMessage[] 之后就将其发送出去（即批量发送所有要发送的邮件）。

 

SimpleEmailSender.java 文件

Java代码  

1. /** 
2.      * 功能: 传入邮件接收者地址列表、标题和内容，然后发送批量邮件服务 
3.      * @param {@link List<String>} receiverList 
4.      * @param {@link String} subject 
5.      * @param {@link String} content 
6.      * @throws MessagingException 
7.      */  
8.     public static void sendBulkEmail(<span style="color: #ff0000;">List<String> receiverList</span>  
9. , String subject, String content) throws MessagingException {  
10.         JavaMailSender sender = (JavaMailSender) mailSender;  
11.         int len = receiverList.size();  
12.         <span style="color: #ff0000;">MimeMessage[] mimeMessageList</span>  
13.  = new MimeMessage[len];    // 注意：是<span style="color: #ff0000;">数组类型</span>  
14.   
15.         MimeMessageHelper messageHelper = null;  
16.           
17.         for(int i = 0; i < len; ++i) {  
18.             <span style="color: #ff0000;">mimeMessageList[i]</span>  
19.  = sender.createMimeMessage();  
20.             messageHelper = new MimeMessageHelper(mimeMessageList[i], true, "UTF-8");  
21.             messageHelper.setFrom("[email protected]");  
22.             messageHelper.setTo(receiverList.get(i));  
23.             messageHelper.setSubject(subject);  
24.             messageHelper.setText(content, true);  
25.         }  
26.           
27.         sender.send(<span style="color: #ff0000;">mimeMessageList</span>  
28. );  
29.     }  

 

UserInfoAction.java 文件

Java代码  

1. // 用户 -> 批量邮件发送  
2. public String sendBatchEmail() {  
3.     if(!emailReceiverList.equals("")) { // 发送用户邮件  
4. /           String[] receiverList = emailReceiverList.split(",");  
5.         <span style="color: #ff0000;">List<String> receiverList</span>  
6. = new ArrayList<String>(20);  
7.         for(int i = 0; i < 20; ++i) {  
8.             receiverList.add("[email protected]");  
9.         }  
10.         long start = System.currentTimeMillis();  
11.         try {  
12. /               SimpleEmailSender.sendBulkEmail(Arrays.asList(receiverList), emailSubject, emailContent);  
13.             SimpleEmailSender.<span style="color: #ff0000;">sendBulkEmail(receiverList</span>  
14.  emailSubject, emailContent);  
15.         } catch (MessagingException e) {  
16.             e.printStackTrace();  
17.         }  
18.         long end = System.currentTimeMillis();  
19.         System.out.println(end - start);  
20.     } else {// 发送用户组邮件  
21.         List<String> receiverList = userInfoService.getUserEmailByGroupId(groupID);  
22.         try {  
23.             SimpleEmailSender.sendBulkEmail(receiverList, emailSubject, emailContent);  
24.         } catch (MessagingException e) {  
25.             e.printStackTrace();  
26.         }  
27.     }  
28.   
29.     return SUCCESS;  
30. }  

 

根据上述两种方案，通过发送 20 封邮件进行测试后发，发现第二种方案（用时 36984 ms）比第一种（81266 ms）的 执行效率 2.1 倍多 。

 

总结

通过这次实验，感觉自己收获了不少。第一，评价哪种方案优劣，用你需要的数据测试就能体现执行效率，但健壮性和可扩展性就不能一概而论了；第二，要想编写更加高效的代码，就必须对你特别重要（特别是常用基础类）的 API 有足够的熟知。就以这个案例为例，刚开始我没有仔细看过 JavaMailSender 的 API ，导致就不知道用 send (MimeMessage [] mimeMessages) 这个函数，所以也不知道存在第二种方案。后来突然发现有这个函数，就像能不能对先前的发送单个邮件服务加以改进，第二种方案也就是这样萌生的。


阅读全文……

发表评论

IT瘾于2014年6月25日 下午06时02分00秒发布 #

 2. 方法二：使用图像打印机（可精确控制像素）

这个方法其实就是添加一个虚拟的打印机，直接将dwg图打印成图片格式。AutoCAD其实提供了这样的虚拟打印机，只是没有默认安装，所以需要手工添加，步骤如下：

接下来的事情，就跟普通的AutoCAD图纸打印无异，不过需要提醒一点的是，在图纸大小的选择上建议根据需要自定义，这样理论上可以得到无限大的（同时也是无限清晰）的图片。比如下图，图纸尺寸定义的是5000×5000像素的，最终保存成图片以后的大小是90多M，已经相当清晰了。

值得强调的是，在添加绘图仪的生产商时并不一定选择光栅文件，另外几种也是可以选择的，这有待读者自己去摸索。这里提供一个@小雄JT（微博地址：http://weibo.com/TRANSzhou）介绍的一个方法：打印成EPS文件。

以下关于EPS的内容来自维基百科EPS条目（地址：http://zh.wikipedia.org/wiki/EPS）。

AutoCAD图输出为EPS格式文件和输出为TIFF图片类似，只是在添加虚拟打印机时需要选择Adobe的PostScript，如下图所示。

虚拟打印后保存的文件，需要使用Photoshop打开，再转换为图片（jpg等）。据@小雄JT 所说，AutoCAD输出的eps文件可以分层，多用在展板或挂图制作上。这种格式的优点就是分辨率高，但缺点是文件也大。

 3. 方法三：PDF转换为图片（PPT使用推荐方法）

还记得如何将PDF转成图片吗？如果不知道的话，请看博客《193·【总结】如何将Office文件转换成图片（买三送一，附…》（地址：http://blog.sina.com.cn/s/blog_638f98570101cnym.html）

至于如何将DWG图转换成PDF文件，我是这样做的：安装PDF虚拟打印机。PDF虚拟打印机有许多种，推荐安装的是pdfFactory。接下来，就是打印图纸的事儿了。方法三相对于方法二来说有一个简便的地方，即可以直接将图片复制到剪切板里面，这样可以将图片粘贴到任何需要的地方。但是方法三又有一个缺点（也算不上吧），即不能精确的控制图片的像素。

 4. 方法四：使用BetterWMF软件（打印报告推荐方法） 

这个方法要用到BetterWMF，那什么是BetterWMF呢？笔者很懒，直接抄软件的使用说明吧：BetterWMF是一款可以将AutoCAD中的DWG图形拷贝到Word中的软件。它的独特之处是在拷贝时可以自动去除那令人烦恼的黑色背景并具有自动修剪图形的空白边缘、自动填充颜色、自动将DWG格式的图形文件转变为WMF图像格式的功能，另外它还能对图形进行缩放、旋转，并能根据使用者的需要对线条的宽度和颜色进行设置。如果你是一位专业制图人员，或者你是一位需要经常编辑制图资料的编辑人员，那么BetterWMF一定可以作为你的首选。嗯，略有广告嫌疑，但我确实不是卖软件的。

BetterWMF常规选线窗口如下图所示。

1、打开“文件(file)”菜单下的“打印机管理器(plottermanager)”。 
2、运行“打印机添加向导（Add-A-Plotter Wizard）。 
3、点击“下一步（next）”，在右边的选项中选择“我的电脑（My Computer）”,继续“下一步”，进入“打印机型号（Plotter Model）”选择页面。 
4、在左边的“厂商（Manufacturers）”中选择“光栅文件格式（Raster File Formats）”，这是我们可以看到在右边的“型号（Model）”中列出了很多种我们熟悉的图形格式，我习惯于使用JPG格式，选择“独立的JPEG编组（Independent JPEG Group JFIF）”，点击“下一步（next）”，直到完成。这样我们以后就可以将CAD图形输出位JPG格式了。接下来我们来看看该如何使用它。 
5、用CAD做好一幅图后，我们打开“文件(file)”菜单下的“打印（plotter...）”。在打印对话框中，在打印机类型中选择我们刚刚装好的“Independent JPEG Group JFIF”，在下面的“打印到文件（plot to file）”里添上生成的文件名称和路径，这个文件就是一个可以再photoshop中编辑的图形了。在页面设置中选择一个我们需要的尺寸，其他的就和使用真正的打印机方法是一样的。点击打印后，等几秒钟，图形就生成了。 

注：系统默认的页面尺寸只有1280*1600，这个尺寸并不能满足我们的需要。我们可以在打印机的属性中自定义我们所需要的尺寸。

阅读全文……

发表评论

IT瘾于2014年6月23日 下午11时51分00秒发布 #

最短路径问题的Dijkstra算法 

是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树>    。该算法常用于路由算法或者作为其他图算法的一个子模块。 

# Dijkstra's algorithm for shortest paths
# David Eppstein, UC Irvine, 4 April 2002

# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
from priodict import priorityDictionary

def Dijkstra(G,start,end=None):
	"""
	Find shortest paths from the  start vertex to all vertices nearer than or equal to the end.

	The input graph G is assumed to have the following representation:
	A vertex can be any object that can be used as an index into a dictionary.
	G is a dictionary, indexed by vertices.  For any vertex v, G[v] is itself a dictionary,
	indexed by the neighbors of v.  For any edge v->w, G[v][w] is the length of the edge.
	This is related to the representation in <http://www.python.org/doc/essays/graphs.html>
	where Guido van Rossum suggests representing graphs as dictionaries mapping vertices
	to lists of outgoing edges, however dictionaries of edges have many advantages over lists:
	they can store extra information (here, the lengths), they support fast existence tests,
	and they allow easy modification of the graph structure by edge insertion and removal.
	Such modifications are not needed here but are important in many other graph algorithms.
	Since dictionaries obey iterator protocol, a graph represented as described here could
	be handed without modification to an algorithm expecting Guido's graph representation.

	Of course, G and G[v] need not be actual Python dict objects, they can be any other
	type of object that obeys dict protocol, for instance one could use a wrapper in which vertices
	are URLs of web pages and a call to G[v] loads the web page and finds its outgoing links.
	
	The output is a pair (D,P) where D[v] is the distance from start to v and P[v] is the
	predecessor of v along the shortest path from s to v.
	
	Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive.
	This code does not verify this property for all edges (only the edges examined until the end
	vertex is reached), but will correctly compute shortest paths even for some graphs with negative
	edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.
	"""

	D = {}	# dictionary of final distances
	P = {}	# dictionary of predecessors
	Q = priorityDictionary()	# estimated distances of non-final vertices
	Q[start] = 0
	
	for v in Q:
		D[v] = Q[v]
		if v == end: break
		
		for w in G[v]:
			vwLength = D[v] + G[v][w]
			if w in D:
				if vwLength < D[w]:
					raise ValueError, "Dijkstra: found better path to already-final vertex"
			elif w not in Q or vwLength < Q[w]:
				Q[w] = vwLength
				P[w] = v
	
	return (D,P)
			
def shortestPath(G,start,end):
	"""
	Find a single shortest path from the given start vertex to the given end vertex.
	The input has the same conventions as Dijkstra().
	The output is a list of the vertices in order along the shortest path.
	"""

	D,P = Dijkstra(G,start,end)
	Path = []
	while 1:
		Path.append(end)
		if end == start: break
		end = P[end]
	Path.reverse()
	return Path

# example, CLR p.528
G = {'s': {'u':10, 'x':5},
	'u': {'v':1, 'x':2},
	'v': {'y':4},
	'x':{'u':3,'v':9,'y':2},
	'y':{'s':7,'v':6}}

print Dijkstra(G,'s')
print shortestPath(G,'s','v')

阅读全文……

发表评论

IT瘾于2014年6月22日 上午01时16分00秒发布 #

广州基础养老金、个人账户养老金、过渡性养老金、过渡性调节金分别按下列办法计算：

　　定义：以当地上年度在岗职工月平均工资和本人指数化月平均缴费工资的平均值为基数，缴费每满1年发给1%。

　　计算公式为：基础养老金=(参保人员退休时当地上年度在岗职工月平均工资+本人指数化月平均缴费工资)÷2×缴费年限×1%

　　其中：指数化月平均缴费工资=当地上年度在岗职工月平均工×本人平均缴费指数

　　个人的平均缴费指数：

阅读全文……

发表评论

IT瘾于2014年6月22日 上午12时58分00秒发布 #

Chart interactivity

If you are looking to add interaction as a layer to charts, Chart.js is not the library for you. A better option would be using SVG, as this will let you attach event listeners to any of the elements in the chart, as these are all DOM nodes.

Chart.js uses the canvas element, which is a single DOM node, similar in characteristics to a static image. This does mean that it has a wider scope for compatibility, and less memory implications than SVG based charting solutions. The canvas element also allows for saving the contents as a base 64 string, allowing saving the chart as an image.

In SVG, all of the lines, data points and everything you see is a DOM node. As a result of this, complex charts with a lot of intricacies, or many charts on the page will often see dips in performance when scrolling or generating the chart, especially when there are multiple on the page. SVG also has relatively poor mobile support, with Android not supporting SVG at all before version 3.0, and iOS before 5.0. (caniuse.com/svg-html5).

Browser support

Browser support for the canvas element is available in all modern & major mobile browsers (caniuse.com/canvas).

For IE8 & below, I would recommend using the polyfill ExplorerCanvas - available at https://code.google.com/p/explorercanvas/. It falls back to Internet explorer's format VML when canvas support is not available. Example use:

<head> 	<!--[if lte IE 8]> 		<script src="excanvas.js"></script> 	<![endif]--> </head>

Usually I would recommend feature detection to choose whether or not to load a polyfill, rather than IE conditional comments, however in this case, VML is a Microsoft proprietary format, so it will only work in IE.

Some important points to note in my experience using ExplorerCanvas as a fallback.

• Initialise charts on load rather than DOMContentReady when using the library, as sometimes a race condition will occur, and it will result in an error when trying to get the 2d context of a canvas.
• New VML DOM elements are being created for each animation frame and there is no hardware acceleration. As a result animation is usually slow and jerky, with flashing text. It is a good idea to dynamically turn off animation based on canvas support. I recommend using the excellentModernizr to do this.
• When declaring fonts, the library explorercanvas requires the font name to be in single quotes inside the string. For example, instead of your scaleFontFamily property being simply "Arial", explorercanvas support, use "'Arial'" instead. Chart.js does this for default values.
•  

阅读全文……

发表评论

IT瘾于2014年6月16日 下午10时58分00秒发布 #

<iframe name="frame1" id="frame1" src="frm.html" frameborder="1" height="30"></iframe>
<p>
    iframe1中文本框的值:</p>
<p>
    <input type="button" name="Submit" value="getValue" onclick="getValue()" />
</p>

<script type="text/javascript">
function getValue(){
    var ofrm1 = document.getElementById("frame1").document;    
    if (ofrm1==undefined)
    {
        ofrm1 = document.getElementById("frame1").contentWindow.document;
        var ff = ofrm1.getElementById("txt1").value;
        alert("firefox/chrome取值结果为:" + ff);
    }
    else
    {
        var ie = document.frames["frame1"].document.getElementById("txt1").value;
        alert("ie取值结果为:" + ie);
    } 
}
</script>

试一试下面标准写法：

window.frames["yourFrame"].yourFunction(); 

阅读全文……

发表评论

IT瘾于2014年6月12日 下午06时11分00秒发布 #

Carrot² is an Open Source Search Results Clustering Engine. It can automatically organize small collections of documents (search results but not only) into thematic categories.

Search results clustered with Carrot² (live demo)

Apart from two specialized document clustering algorithms, Carrot²offers ready-to-use components for fetching search results from various sources including GoogleAPI, Bing API, eTools Meta Search, Lucene, SOLR, and more.

Carrot² is implemented in Java, but a native C# / .NET API is also available. Other non-Java platforms, such as PHP or Ruby, can call Carrot² clustering through its REST interface. The downloads page will help you to choose the right package. For consulting services, installation, maintenance and text mining expertise, contact Carrot Search -- the Carrot² spin-off company.

阅读全文……

发表评论

IT瘾于2014年6月8日 上午01时13分00秒发布 #

B-树

1 .B-树定义

B-树是一种平衡的多路查找树，它在文件系统中很有用。

定义：一棵m 阶的B-树，或者为空树，或为满足下列特性的m 叉树：
⑴树中每个结点至多有m 棵子树；
⑵若根结点不是叶子结点，则至少有两棵子树；

⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树；
⑷所有的非终端结点中包含以下信息数据：

      （n，A0，K1，A1，K2，…，Kn，An）
其中：Ki（i=1,2,…,n）为关键码，且Ki<Ki+1，

           Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn.

           n   为关键码的个数。
⑸所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

   即所有叶节点具有相同的深度，等于树高度。

 如一棵四阶B-树，其深度为4.

B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。

在上图的B-树上查找关键字47的过程如下：

1）首先从更开始，根据根节点指针找到 *节点，因为 *a 节点中只有一个关键字，且给定值47 > 关键字35，则若存在必在指针A1所指的子树内。

2）顺指针找到 *c节点，该节点有两个关键字（43和 78），而43 < 47 < 78,若存在比在指针A1所指的子树中。

3）同样，顺指针找到 *g节点，在该节点找到关键字47,查找成功。

2. 查找算法

B- 树查找算法分析

从查找算法中可以看出， 在B- 树中进行查找包含两种基本操作:

        ( 1) 在B- 树中查找结点；

        ( 2) 在结点中查找关键字。

       由于B- 树通常存储在磁盘上， 则前一查找操作是在磁盘上进行的， 而后一查找操作是在内存中进行的， 即在磁盘上找到指针p 所指结点后， 先将结点中的信息读入内存， 然后再利用顺序查找或折半查找查询等于K 的关键字。显然， 在磁盘上进行一次查找比在内存中进行一次查找的时间消耗多得多.

      因此， 在磁盘上进行查找的次数、即待查找关键字所在结点在B- 树上的层次树， 是决定B树查找效率的首要因素

        那么，对含有n 个关键码的m 阶B-树，最坏情况下达到多深呢？可按二叉平衡树进行类似分析。首先，讨论m 阶B-数各层上的最少结点数。

       由B树定义：B树包含n个关键字。因此有n+1个树叶都在第J+1 层。

    1）第一层为根，至少一个结点，根至少有两个孩子，因此在第二层至少有两个结点。

    2）除根和树叶外，其它结点至少有[m/2]个孩子,因此第三层至少有2*[m/2]个结点,在第四层至少有2*[m/2]2 个结点…

    3）那么在第J+1层至少有2*[m/2]J-1个结点,而J+1层的结点为叶子结点,于是叶子结点的个数n+1。有：

        也就是说在n个关键字的B树查找，从根节点到关键字所在的节点所涉及的节点数不超过：

3.B-树的插入

  B^-树的生成也是从空树起，逐个插入关键字而得。但由于B^-树结点中的关键字个数必须≥ceil(m／2)-1，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”，

如图（a） 为3阶的B^-树(图中略去F结点(即叶子结点))，假设需依次插入关键字30，26，85。

1) 首先通过查找确定插入的位置。由根*a 起进行查找，确定30应插入的在*d 节点中。由于*d 中关键字数目不超过2（即m-1），故第一个关键字插入完成：如（b）

2) 同样，通过查找确定关键字26亦应插入 *d. 由于*d节点关键字数目超过2，此时需要将 *d分裂成两个节点，关键字26及其前、后两个指针仍保留在 *d 节点中，而关键字37 及其前、后两个指针存储到新的产生的节点 *d` 中。同时将关键字30 和指示节点 *d `的指针插入到其双亲的节点中。由于 *b节点中的关键字数目没有超过2，则插入完成.如（c）(d)

3) (e) -(g) 为插入85后;

插入算法：

4. B-树的删除

      反之，若在B^-树上删除一个关键字，则首先应找到该关键字所在结点，并从中删除之，若该结点为最下层的非终端结点，且其中的关键字数目不少于ceil(m/2)，则删除完成，否则要进行“合并”结点的操作。假若所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y替代Ki，然后在相应的结点中删去Y。例如，在下图  图4.1( a)的B^-树上删去45，可以*f结点中的50替代45，然后在*f结点中删去50。

                                图4.1( a)

因此，下面我们可以只需讨论删除最下层非终端结点中的关键字的情形。有下列三种可能：

    (1)被删关键字所在结点中的关键字数目不小于ceil(m/2)，则只需从该结点中删去该关键字Ki和相应指针Ai，树的其它部分不变，例如，从图  图4.1( a)所示B^-树中删去关键字12，删除后的B^-树如图  图4.2( a)所示：

                           图4.2( a)

   (2)被删关键字所在结点中的关键字数目等于ceil(m/2)-1，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1，则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。

[例如]，从图图4.2( a)中删去50，需将其右兄弟结点中的61上移至*e结点中，而将*e结点中的53移至*f，从而使*f和*g中关键字数目均不小于ceil(m-1)-1，而双亲结点中的关键字数目不变，如图图4.2(b)所示。

                               图4.2(b)

       (3)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于ceil(m/2)-1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到 Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点中)。

[例如]，从图4.2(b)所示 B^-树中删去53，则应删去*f结点，并将*f中的剩余信息(指针“空”)和双亲*e结点中的 61一起合并到右兄弟结点*g中。删除后的树如图4.2(c)所示。

                                图4.2(c)

 如果因此使双亲结点中的关键字数目小于ceil(m/2)-1，则依次类推。

[例如]，在 图4.2(c)的B-树中删去关键字37之后，双亲b结点中剩余信息(“指针c”)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中，删除后的B^-树如图 4.2(d)所示。  

                         图 4.2(d)

B-树主要应用在文件系统

为了将大型数据库文件存储在硬盘上 以减少访问硬盘次数为目的 在此提出了一种平衡多路查找树——B-树结构 由其性能分析可知它的检索效率是相当高的 为了提高 B-树性能’还有很多种B-树的变型，力图对B-树进行改进

B+树

      B+树是应文件系统所需而产生的一种B-树的变形树。一棵m 阶的B+树和m 阶的B-
树的差异在于：
⑴有n 棵子树的结点中含有n 个关键码；
⑵所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且
叶子结点本身依关键码的大小自小而大的顺序链接。
⑶所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。

B+树在数据库中的应用

1. 索引在数据库中的作用 

        在数据库系统的使用过程当中，数据的查询是使用最频繁的一种数据操作。

        最基本的查询算法当然是顺序查找（linear search），遍历表然后逐行匹配行值是否等于待查找的关键字，其时间复杂度为O（n）。但时间复杂度为O（n）的算法规模小的表，负载轻的数据库，也能有好的性能。  但是数据增大的时候，时间复杂度为O（n）的算法显然是糟糕的，性能就很快下降了。

       好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

       索引是对数据库表 中一个或多个列的值进行排序的结构。与在表 中搜索所有的行相比，索引用指针 指向存储在表中指定列的数据值，然后根据指定的次序排列这些指针，有助于更快地获取信息。通常情 况下 ，只有当经常查询索引列中的数据时 ，才需要在表上创建索引。索引将占用磁盘空间，并且影响数 据更新的速度。但是在多数情况下 ，索引所带来的数据检索速度优势大大超过它的不足之处。

2. B+树在数据库索引中的应用

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构

1）在数据库索引的应用

在数据库索引的应用中，B+树按照下列方式进行组织   ：

①  叶结点的组织方式 。B+树的查找键 是数据文件的主键 ，且索引是稠密的。也就是说 ，叶结点 中为数据文件的第一个记录设有一个键、指针对 ，该数据文件可以按主键排序，也可以不按主键排序 ；数据文件按主键排序，且 B +树是稀疏索引 ，  在叶结点中为数据文件的每一个块设有一个键、指针对 ；数据文件不按键属性排序 ，且该属性是 B +树 的查找键 ， 叶结点中为数据文件里出现的每个属性K设有一个键 、 指针对 ， 其中指针执行排序键值为 K的 记录中的第一个。

② 非叶结点 的组织方式。B+树 中的非叶结点形成 了叶结点上的一个多级稀疏索引。  每个非叶结点中至少有ceil( m/2 ) 个指针 ， 至多有 m 个指针 。  

2）B+树索引的插入和删除

①在向数据库中插入新的数据时，同时也需要向数据库索引中插入相应的索引键值 ，则需要向 B+树 中插入新的键值。即上面我们提到的B-树插入算法。

②当从数据库中删除数据时，同时也需要从数据库索引中删除相应的索引键值 ，则需要从 B+树 中删 除该键值 。即B-树删除算法

为什么使用B-Tree（B+Tree）

     二叉查找树进化品种的红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。

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

       局部性原理与磁盘预读

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

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

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

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

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

      我们上面分析B-/+Tree检索一次最多需要访问节点：

     h =

      数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B- Tree还需要使用如下技巧：

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

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

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

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

MySQL的B-Tree索引（技术上说B+Tree）

       在 MySQL 中，主要有四种类型的索引，分别为： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引。

        B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型，除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引，而且只支持索引单个 AUTO_INCREMENT 列。

       不仅仅在 MySQL 中是如此，实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型，这主要是因为 B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。

     一般来说， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的，也就是所有实际需要的数据都存放于 Tree 的 Leaf Node(叶子节点) ，而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的，所以我们大家都称之为 B-Tree 索引。当然，可能各种数据库（或 MySQL 的各种存储引擎）在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree，也就是在 B-Tree 数据结构的基础上做了很小的改造，在每一个Leaf Node 上面出了存放索引键的相关信息之外，还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息（增加了顺序访问指针），这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。

下面主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式：

1. MyISAM索引实现：

1）主键索引：

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图：

                                                                           （图myisam1）

这里设表一共有三列，假设我们以Col1为主键，图myisam1是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

2）辅助索引（Secondary key）

在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
  

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

2. InnoDB索引实现

然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同.

1）主键索引：

         MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

               (图inndb主键索引）

(图inndb主键索引）是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

2）. InnoDB的辅助索引

       InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

        InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过，它的辅助索引（Secondary Index， 也就是非主键索引）也会包含主键列，所以，如果主键定义的比较大，其他索引也将很大。如果想在表上定义 、很多索引，则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。

      文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

      不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

 InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

阅读全文……

发表评论

IT瘾于2014年6月6日 上午07时11分00秒发布 #

    3.3文件查找的具体过程(涉及磁盘IO操作)

为了简单，这里用少量数据构造一棵3叉树的形式，实际应用中的B树结点中关键字很多的。上面的图中比如根结点，其中17表示一个磁盘文件的文件名；小红方块表示这个17文件内容在硬盘中的存储位置；p1表示指向17左子树的指针。

其结构可以简单定义为：

typedef struct {

    /*文件数*/

    int  file_num;

    /*文件名(key)*/

    char * file_name[max_file_num];

    /*指向子节点的指针*/

     BTNode * BTptr[max_file_num+1];

     /*文件在硬盘中的存储位置*/

     FILE_HARD_ADDR offset[max_file_num];

}BTNode;

假如每个盘块可以正好存放一个B树的结点（正好存放2个文件名）。那么一个BTNODE结点就代表一个盘块，而子树指针就是存放另外一个盘块的地址。

下面，咱们来模拟下查找文件29的过程：

1. 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作 1次】    
2. 此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针p2。
3. 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作 2次】    
4. 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针p2。
5. 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作 3次】    
6. 此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。

分析上面的过程，发现需要3次磁盘IO操作和3次内存查找操作。关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。

当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘4次，最多5次，而且文件越多，B树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高。

阅读全文……

发表评论

IT瘾于2014年6月6日 上午07时08分00秒发布 #