R TREE学习借鉴之路

20170104

在trajectory中，R tree是基础，看了论文不是特别明白，看下博客，进一步理解：

1.  http://blog.csdn.net/v_JULY_v/article/details/6530142/ 比较清楚讲解的link然后，在内部里面，阅读联想b tree提到的仅包含key 在Non leaf 节点的举例，前后联想R TREE，融会贯通

2. 代码实现部分，忘了typedef struct用法，顺便复习一下。http://www.kuqin.com/language/20090406/44443.html

typedef struct tagMyStruct
{ 
　int iNum;
　long lLength;
} MyStruct;

3. 

数组指针（也称行指针）
定义 int (*p)[n];
()优先级高，首先说明p是一个指针，指向一个整型的一维数组，这个一维数组的长度是n，也可以说是p的步长。也就是说执行p+1时，p要跨过n个整型数据的长度。

如要将二维数组赋给一指针，应这样赋值：
int a[3][4];
int (*p)[4]; //该语句是定义一个数组指针，指向含4个元素的一维数组。
 p=a;        //将该二维数组的首地址赋给p，也就是a[0]或&a[0][0]
 p++;       //该语句执行过后，也就是p=p+1;p跨过行a[0][]指向了行a[1][]

所以数组指针也称指向一维数组的指针，亦称行指针。

指针数组
定义 int *p[n];
[]优先级高，先与p结合成为一个数组，再由int*说明这是一个整型指针数组，它有n个指针类型的数组元素。这里执行p+1是错误的，这样赋值也是错误的：p=a；因为p是个不可知的表示，只存在p[0]、p[1]、p[2]...p[n-1],而且它们分别是指针变量可以用来存放变量地址。但可以这样 *p=a; 这里*p表示指针数组第一个元素的值，a的首地址的值。
如要将二维数组赋给一指针数组:
int *p[3];
int a[3][4];
for(i=0;i<3;i++)
p[i]=a[i];
这里int *p[3] 表示一个一维数组内存放着三个指针变量，分别是p[0]、p[1]、p[2]
所以要分别赋值。

这样两者的区别就豁然开朗了，数组指针只是一个指针变量，似乎是C语言里专门用来指向二维数组的，它占有内存中一个指针的存储空间。指针数组是多个指针变量，以数组形式存在内存当中，占有多个指针的存储空间。
还需要说明的一点就是，同时用来指向二维数组时，其引用和用数组名引用都是一样的。
比如要表示数组中i行j列一个元素：
*(p[i]+j)、*(*(p+i)+j)、(*(p+i))[j]、p[i][j]

 

优先级：()>[]>*

20170106:

接下来继续看r-tree:自己理解融合

1. b-tree 每个节点的信息，存储的是对应的key +value可以携带，但是，具体的，要记忆那个图，多体会。

而在b+ tree里面，中间部分，存储的就是，对应的index索引部分。

2. ceil 函数作用：ceil函数的作用是求不小于给定实数的最小整数。

3. 最后B TREE定义里面的叶子节点不含有任何关键字等信息，指的是最后null指针下面所指向的最后节点。

4.看完之后，联想总结下，自己对于B-TREE, B++ TREE整体的理解，区别，对比，优势（B + TREE 不带有任何相关的 real value在中间节点中）

5. tuple identifier在叶子节点中，是N维的矩阵向量相关：

先来探究一下叶子结点的结构。叶子结点所保存的数据形式为：(I, tuple-identifier)。

      其中，tuple-identifier表示的是一个存放于数据库中的tuple，也就是一条记录，它是n维的。I是一个n维空间的矩形，并可以恰好框住这个叶子结点中所有记录代表的n维空间中的点。I=(I₀,I₁,…,I_n-1)。---在这张图中，I所代表的就是图中的矩形，其范围是a<=I₀<=b，c<=I₁<=d。有两个tuple-identifier，在图中即表示为那两个点。--体会其中的变化分析。

6.看完之后，对R-TREE B-TREE, B+-TREE有了全新的理解，这点要注意进行体会。---下面就准备看论文，重新梳理结构和YUZHENG INDEX建立相关

7。 20170108：看完了guttman对应的r tree文章，有了全新的理解，进一步深化对应的理解运用分析。需要注意几点：

a.R TREE的构造由来，为什么要构造R TREE，理由是什么，如何从b tree中进行延伸的，注意体会变化分析。

b。基本的元素，tuple child data identifier 这些都要注意，领会。并且，清楚地记忆对应的图形。

c.在定义完基本的元素之后，就开始定义对应的操作（逻辑非常强烈，注意学习体会，比如insert, delete,choose  leaf, adjust leaf, node split【其中对应有三种算法，每种方式 都不相同，注意体会其中的变化方式，这点非常的重要。exhaustive, quadratic linear.其中Linear 于quadratic 的不同，在于seed select其中的变化，就注意体会了。】）

d. 具体implementation上，有不同的对应方式，有一篇PDF 来自thu的网站，后续做具体的Implementation可以关注下。

e。思考这篇文章到底在做什么，到底实现了什么，有什么对应的意义，如何进行对应的优化分析，来进一步优化对应的模型，实现performance的提升，这些都需要思考的。

f。看论文注意对应的总结提升，来进一步的优化求解。