B+ tree and B-tree

B+ tree (BplusTree)

基本:
a balanced tree
从树的根到每个叶子结点路径长度相同
每个非叶结点有 n/2~n 个子结点
对于查询效率较高，但浪费一定的空间
每个典型的结点包含多达 n-1 个key :k1 k2 .. kn-1 和 n个指针 p1 p2 .. pn
查询的key值是顺利存储
p1 k1 p2 k2 .. pn-1 kn-1 pn
指针可以指向一个文件的某条记录或是某条指针（指向其他文件的记录）

每个叶子结点最多能够保存 (n - 1) 个值，但最少 [(n – 1) / 2] 个值
非叶结点指向树的叶结点，非叶结点至少有 n/2 个指针

更新
insert
do a search to determine what bucket the new record should go in
if the bucket is not full, add the record.
otherwise, split the bucket.
allocate new leaf and move half the bucket's elements to the new bucket
insert the new leaf's smallest key and address into the parent.
if the parent is full, split it also
now add the middle key to the parent node
repeat until a parent is found that need not split
if the root splits, create a new root which has one key and two pointers.

delete
It removes the search key value from the node.

文件存储结构
the leaf nodes of the tree stores the actual record

During insertion, the system locates the block that should contain the record. If there is enough free space in the node then the system stores it. Otherwise the system splits the record in two and distributes the records.

During deletion, the system first removes the record from the block containing it. If the block becomes less than half full as a result, the records in the block are redistributed.



perl 的B+tree实现Tree::BPTree

B - Tree Index Files
未完

处理xml一例

#!/usr/bin/perl
use strict;
use XML::Simple;
use Data::Dumper;
use warnings;

my $xmlfile = $ARGV[0];
my $ref = XMLin("$xmlfile",ForceArray=>1);
my $xmlname = `basename $xmlfile`;

my $Country ;
($Country = $xmlname ) =~ s/-\d+\.xml//g;
chop($Country);

my %prodprophash = (
"de" => "Produkteigenschaften",
"uk" => "Product properties",
"ca" => "Product properties",
"us" => "Product properties",
"es" => "Product properties",
"fr" => "Caract.ristiques du produit");

my $PROPerty = $prodprophash{"$Country"};
my $errnum = 0;my $warnnum = 0;
foreach (@{$ref->{'product'}}){
print "="x25,"\n";
print "Country : \"",$Country,"\"\n";
print "category id:";
print $_->{'category-id'}->[0],"\n";
print "Product id :"; print $_->{id}->[0],"\n";
my $ImgCheck="N";
my $ImgCheck="N";
if (exists($_->{'image-url'}->[0] ) )
{
if( !( ($_->{'image-url'}->[0]->{'content'} ne "") && ($_->{'image-url'}->[0]->{'content'} =~ /^http:\/\/www.abc.com\/product/)) )
...

[ array标记
{ hash标记

外层用SHELL调用
在特定目录下，循环利用 0000~0029 目录，利用一个文件来保存最后写入的文件夹名称

if [ x"$2" != x ]
then
tmpdir="$2"
downloadXml="N"
else
downloadXml="Y"

if ! [ -d "$batchDir" ]
then
mkdir -p "$batchDir"
echo "0" > "$batchDir"/lastBatchId.txt
fi

temp=$(expr $(cat "$batchDir"/lastBatchId.txt) + 1)
batchId=$(expr $temp % 30 )
batchIdDir=$(printf "%04d" $batchId)

if [ -d "$batchDir"/"$batchIdDir" ]
then
rm -rf "$batchDir"/"$batchIdDir"
fi

mkdir -p "$batchDir"/"$batchIdDir"
echo $(expr $batchId) > "$batchDir"/lastBatchId.txt

tmpdir="$batchDir"/"$batchIdDir"
fi

UTF-8

from wiki

設計UTF-8的理由
UTF-8的設計有以下的多字元組序列的特質：
單位元組字符的最高有效位元永遠為0。
多位元組序列中的首個字元組的幾個最高有效位元決定了序列的長度。最高有效位為110的是2位元組序列，而1110的是三位元組序列，如此類推。
多位元組序列中其餘的位元組中的首兩個最高有效位元為10。
UTF-8的這些特質，保證了一個字符的位元組序列不會包含在另一個字符的位元組序列中。這確保了以位元組為基礎的部份字串比對（sub-string match）方法可以適用於在文字中搜尋字或詞。有些比較舊的可變長度8位元編碼（如Shift JIS）沒有這個特質，故字串比對的算法變得相當複雜。雖然這增加了UTF-8編碼的字串的信息冗餘，但是利多於弊。另外，資料壓縮並非Unicode 的目的，所以不可混為一談。即使在傳送過程中有部份位元組因錯誤或干擾而完全遺失，還是有可能在下一個字符的起點重新同步，令受損範圍受到限制。
另一方面，由於其位元組序列設計，如果一個疑似為字符串的序列被驗證為UTF-8編碼，那麼我們可以有把握地說它是UTF-8字符串。一段兩位元組隨機序列碰巧為合法的UTF-8而非ASCII 的機率為32分1。對於三位元組序列的機率為256分3，對更長的序列的機率就更低了。

优点及缺点
关于字符串长度的一个注解：
总体来说，在Unicode字符串中不可能由码点数量决定显示它所需要的长度，或者显示字符串之后在文本缓冲区中光标应该放置的位置；组合字符、变宽字体、不可打印字符和从右至左的文字都是其归因。
所以尽管在UTF-8字符串中字元数量与码点数量的关系比UTF-32更为复杂，在实际中很少会遇到有不同的情形。
总体
优点
UTF-8是ASCII的一个超集。因为一个纯ASCII字符串也是一个合法的UTF-8字符串，所以现存的ASCII文本不需要转换。为传统的扩展ASCII字符集设计的软件通常可以不经修改或很少修改就能与UTF-8一起使用。
使用标准的面向字节的排序例程对UTF-8排序将产生与基于Unicode代码点排序相同的结果。（尽管这只有有限的有用性，因为在任何特定语言或文化下都不太可能有仍可接受的文字排列顺序。）
UTF-8和UTF-16都是可扩展标记语言文档的标准编码。所有其它编码都必须通过显式或文本声明来指定。[2]
任何面向字节的字符串搜索算法都可以用于UTF-8的数据（只要输入仅由完整的UTF-8字符组成）。但是，对于包含字符记数的正则表达式或其它结构必须小心。
UTF-8字符串可以由一个简单的算法可靠地识别出来。就是，一个字符串在任何其它编码中表现为合法的UTF-8的可能性很低，并随字符串长度增长而减小。举例说，字元值C0,C1,F5至FF从来没有出现。为了更好的可靠性，可以使用正则表达式来统计非法过长和替代值（可以查看W3 FAQ: Multilingual Forms上的验证UTF-8字符串的正则表达式）。
缺点
一份写得很差（并且与当前标准的版本不兼容）的UTF-8解析器可能会接受一些不同的伪UTF-8表示并将它们转换到相同的Unicode输出上。这为设计用于处理八位表示的校验例程提供了一种遗漏信息的方式。

使用UTF-8的原因
ASCII轉换成UCS-2，在編碼前插入一個0x0。用這些編碼，會含括一些控制符，比如 " 或 '/'，這在UNIX和一些C函數中，將會産生嚴重錯誤。因此可以肯定，UCS-2不適合作為Unicode的外部編碼，也因此誕生了UTF-8。

不利于正则表达式检索
正则表达式可以进行很多英文高级的模糊检索。例如，[a-h]表示a到h间所有字母。
同样GBK编码的中文也可以这样利用正则表达式，比如在只知道一个字的读音而不知道怎么写的情况下，也可用正则表达式检索，因为GBK编码是按读音排序的。只是UTF-8不是按读音排序的，所以会对正则表达式检索造成不利影响。但是這種使用方式並未考慮中文中的破音字，因此影響不大。Unicode是按部首排序的，因此在只知道一個字的部首而不知道如何發音的情况下，UTF-8 可用正则表达式检索而GBK不行。

其他
與其他 Unicode 編碼相比，特別是UTF-16，在 UTF-8 中 ASCII 字元佔用的空間只有一半，可是在一些字元的 UTF-8 編碼佔用的空間就要多出，特別是中文、日文和韓文（CJK）這樣的象形文字，所以具體因素因文檔而異，但不論哪種情況，差別都不可能很明顯。

utf8_unicode_ci 和 utf8_general_ci 区别
在 phpMyAdmin 中有多种字符集，其中 utf8_unicode_ci 和 utf8_general_ci 是最常用的，但是 utf8_general_ci 对某些语言的支持有一些小问题，如果可以接受，那最好使用 utf8_general_ci ，因为它速度快。否则，请使用较为精确的 utf8_unicode_ci，不过速度会慢一些。

数据库基础--索引

From baidu baike

使用索引可快速访问数据库表中的特定信息。索引是对数据库表中一列或多列的值进行排序的一种结构，例如 employee 表的姓（lname）列。如果要按姓查找特定职员，与必须搜索表中的所有行相比，索引会帮助您更快地获得该信息。
　　索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。
　　索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引的方式与您使用书籍中的索引的方式很相似：它搜索索引以找到特定值，然后顺指针找到包含该值的行。
　　在数据库关系图中，您可以在选定表的“索引/键”属性页中创建、编辑或删除每个索引类型。当保存索引所附加到的表，或保存该表所在的关系图时，索引将保存在数据库中。
　　注意 并非所有的数据库都以相同的方式使用索引。作为通用规则，只有当经常查询索引列中的数据时，才需要在表上创建索引。索引占用磁盘空间，并且降低添加、删除和更新行的速度。在多数情况下，索引用于数据检索的速度优势大大超过它的不足之处。但是，如果应用程序非常频繁地更新数据或磁盘空间有限，则可能需要限制索引的数量。
　　可以基于数据库表中的单列或多列创建索引。多列索引使您可以区分其中一列可能有相同值的行。
　　如果经常同时搜索两列或多列或按两列或多列排序时，索引也很有帮助。例如，如果经常在同一查询中为姓和名两列设置判据，那么在这两列上创建多列索引将很有意义。
　　确定索引的有效性：
　　检查查询的 WHERE 和 JOIN 子句。在任一子句中包括的每一列都是索引可以选择的对象。
　　对新索引进行试验以检查它对运行查询性能的影响。
　　考虑已在表上创建的索引数量。最好避免在单个表上有很多索引。
　　检查已在表上创建的索引的定义。最好避免包含共享列的重叠索引。
　　检查某列中唯一数据值的数量，并将该数量与表中的行数进行比较。比较的结果就是该列的可选择性，这有助于确定该列是否适合建立索引，如果适合，确定索引的类型。
　　
建立索引的优点
　　1.大大加快数据的检索速度;
　　2.创建唯一性索引，保证数据库表中每一行数据的唯一性;
　　3.加速表和表之间的连接;
　　4.在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。
　　
索引的缺点
　　1.索引需要占物理空间。
　　2.当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。


索引列
　　
　　可以基于数据库表中的单列或多列创建索引。多列索引使您可以区分其中一列可能有相同值的行。
　　
索引类型
　　根据数据库的功能，可以在数据库设计器中创建三种索引：唯一索引、主键索引和聚集索引。有关数据库所支持的索引功能的详细信息，请参见数据库文档。
　　提示 尽管唯一索引有助于定位信息，但为获得最佳性能结果，建议改用主键或唯一约束。有关这些约束的更多信息，请参见主键约束和唯一约束。
　　唯一索引
　　唯一索引是不允许其中任何两行具有相同索引值的索引。
　　当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如，如果在 employee 表中职员的姓 (lname) 上创建了唯一索引，则任何两个员工都不能同姓。
　　有关唯一索引的更多信息，请参见创建唯一索引。
　　主键索引
　　数据库表经常有一列或列组合，其值唯一标识表中的每一行。该列称为表的主键。
　　在数据库关系图中为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访问。有关主键的更多信息，请参见定义主键。
　　聚集索引
　　在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引。
　　如果某索引不是聚集索引，则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比，聚集索引通常提供更快的数据访问速度。