xiaobaoqiu Blog

Think More, Code Less

R Tree

1.R-Tree简介

Btree以及它的变体B+tree对数据库的发展可谓是功不可没,但是,Btree良好的性能却仅仅只能在一维数据上产生效果,如果涉及到二维数据甚至多维数据,那么Btree也无能为力了。然而随着GIS(地理信息系统)和CAD(计算机辅助设计)的广泛应用,多维空间数据(spatial data)的处理变得相当普遍,因此必须在二维和多维数据上找到一种有效的索引方法,于是Rtree就出现了.

1984年,加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial searching”的论文,向世人介绍了R树这种处理高维空间存储问题的数据结构。

简单的说,就是将空间对象按某种空间关系进行划分,以后对空间对象的存取都基于划分块进行。

2.R-Tree原理

R树是一种多级平衡树,它是B树在多维空间上的扩展。在R树中存放的数据并不是原始数据,而是这些数据的最小边界矩形(Minimal-Bounding-Box, MBR),空间对象的MBR被包含于R树的叶结点中。从叶子结点开始用矩形(rectangle)将空间框起来,父节点的矩形需要包含字节点的矩形,结点越往上框住的空间就越大,以此对空间进行分割。

下图展示了一些列对象的边界矩形:

一个矩形框住一个或者多个节点,比如矩形R8框的是一个不规则对象,而矩形R6包含了矩形R15和R16;

R-Tee满足以下属性:

  1. 每个叶子节点包含m到M个索引记录,除非它是根节点;
  2. 每个叶子节点的索引记录(I, tuple-identifier),I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形(高维空间矩形).
  3. 每个非叶子节点包含m到M个子节点,除非它是根节点;
  4. 对于在非叶子结点上的每一个条目(Entry),I是最小的可以在空间中完全包含所有子节点矩形的最小矩形;
  5. 根节点至少有两个孩子节点,除非它是叶子节点;
  6. 所有的叶子节点在同一层;

需要保证,m <= M/2;

叶子节点:

叶子结点所保存的数据形式为:(I, tuple-identifier),其中,tuple-identifier表示的是一个存放于数据库中的tuple,也就是一条记录,它是n维的。I是一个n维空间的矩形,它可以恰好框住这个叶子结点中所有记录代表的n维空间中的点。

非叶子节点

叶子结点所保存的数据形式为:(I, child-pointer),其中child-pointer是子节点指针,I是可以覆盖所有子节点的最小n维空间的矩形;

3.R-Tree应用

典型的PostGis,这使得Postgresql支持空间索引.

4.R-Tree实现

一个网络上的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
public class RTree<T> {

    public enum SeedPicker {
        LINEAR, QUADRATIC
    }

    /**
     * 每个节点包含的最大entry数目
     */
    private final int M;

    /**
     * 每个节点包含的最小entry数目
     */
    private final int m;

    /**
     * 空间的维度,如平面则为2,空间点则为3
     */
    private final int D;

    private final float[] pointDims;

    private final SeedPicker seedPicker;

    /**
     * 根节点
     */
    private Node root;

    private volatile int size;

    /**
     * 构造默认R-Tree的参数
     * DEFAULT_M : M
     * DEFAULT_m : m
     * DEFAULT_D : D
     */
    private static final int DEFAULT_M = 50;
    private static final int DEFAULT_m = 2;
    private static final int DEFAULT_D = 2;

    /**
     * 创建一颗新的R-Tree
     * 
     * @param M maximum number of entries per node
     * @param m minimum number of entries per node (except for the root node)
     * @param D the number of dimensions of the RTree.
     */
    public RTree(int M, int m, int D, SeedPicker seedPicker) {
        assert (m <= (M / 2));
        this.D = D;
        this.M = M;
        this.m = m;
        this.seedPicker = seedPicker;
        pointDims = new float[D];
        root = buildRoot(true);
    }

    public RTree(int M, int m, int D) {
        this(M, m, D, SeedPicker.LINEAR);
    }

    /**
     * 使用默认参数构造一个R-Tree
     */
    public RTree() {
        this(DEFAULT_M, DEFAULT_m, DEFAULT_D, SeedPicker.LINEAR);
    }

    /**
     * 构造根节点
     *
     * @param asLeaf : 根节点是否为叶子节点
     * @return
     */
    private Node buildRoot(boolean asLeaf) {
        float[] initCoords = new float[D];
        float[] initDimensions = new float[D];
        for (int i = 0; i < this.D; i++) {
            initCoords[i] = (float) Math.sqrt(Float.MAX_VALUE);
            initDimensions[i] = -2.0f * (float) Math.sqrt(Float.MAX_VALUE);
        }
        return new Node(initCoords, initDimensions, asLeaf);
    }

    /**
     * getter
     */
    public int getMaxEntries() {
        return M;
    }

    public int getMinEntries() {
        return m;
    }

    public int getNumDims() {
        return D;
    }

    public int size() {
        return size;
    }

    /**
     * 在R-Tee中搜索和给定矩形有重叠(overlapping)的对象
     * 
     * @param coords 矩形的一个顶点(比如左上角)
     * @param dimensions 矩形长度.
     * 返回对象List,这些对象的最小边界矩形(MBR)和给定矩形重叠
     */
    public List<T> search(float[] coords, float[] dimensions) {
        assert (coords.length == D);
        assert (dimensions.length == D);

        LinkedList<T> results = new LinkedList<T>();
        search(coords, dimensions, root, results);

        return results;
    }

    private void search(float[] coords, float[] dimensions, Node n, LinkedList<T> results) {
        if (n.leaf) {
            for (Node e : n.children) {
                if (isOverlap(coords, dimensions, e.coords, e.dimensions)) {
                    results.add(((Entry) e).entry);
                }
            }
        } else {
            for (Node c : n.children) {
                if (isOverlap(coords, dimensions, c.coords, c.dimensions)) {
                    search(coords, dimensions, c, results); //继续在孩子节点中搜索
                }
            }
        }
    }

    /**
     * 删除R-Tree中在矩形rect内的数据entry
     * 
     * @param coords : 矩形的一个顶点(比如左上角)
     * @param dimensions : 矩形长度
     * @param entry : 待删除数据
     * 删除成功返回true
     */
    public boolean delete(float[] coords, float[] dimensions, T entry) {
        assert (coords.length == D);
        assert (dimensions.length == D);
        Node l = findLeaf(root, coords, dimensions, entry);
        if (l == null) {
            System.out.println("WTF?");
            findLeaf(root, coords, dimensions, entry);
        }
        assert (l != null) : "Could not find leaf for entry to delete";
        assert (l.leaf) : "Entry is not found at leaf?!?";
        ListIterator<Node> li = l.children.listIterator();
        T removed = null;
        while (li.hasNext()) {
            @SuppressWarnings("unchecked")
            Entry e = (Entry) li.next();
            if (e.entry.equals(entry)) {
                removed = e.entry;
                li.remove();
                break;
            }
        }
        if (removed != null) {
            condenseTree(l);
            size--;
        }
        if (size == 0) {
            root = buildRoot(true);
        }
        return (removed != null);
    }

    public boolean delete(float[] coords, T entry) {
        return delete(coords, pointDims, entry);
    }

    /**
     * 查找数据 entry 对应的叶子节点
     * @param n
     * @param coords
     * @param dimensions
     * @param entry
     * @return
     */
    private Node findLeaf(Node n, float[] coords, float[] dimensions, T entry) {
        if (n.leaf) {
            for (Node c : n.children) {
                if (((Entry) c).entry.equals(entry)) {
                    return n;
                }
            }
            return null;
        } else {
            for (Node c : n.children) {
                if (isOverlap(c.coords, c.dimensions, coords, dimensions)) {
                    Node result = findLeaf(c, coords, dimensions, entry);
                    if (result != null) {
                        return result;
                    }
                }
            }
            return null;
        }
    }

    /**
     * 压缩树
     * @param n
     */
    private void condenseTree(Node n) {
        Set<Node> q = new HashSet<Node>();
        while (n != root) {
            if (n.leaf && (n.children.size() < m)) {
                q.addAll(n.children);
                n.parent.children.remove(n);
            } else if (!n.leaf && (n.children.size() < m)) {
                // probably a more efficient way to do this...
                LinkedList<Node> toVisit = new LinkedList<Node>(n.children);
                while (!toVisit.isEmpty()) {
                    Node c = toVisit.pop();
                    if (c.leaf) {
                        q.addAll(c.children);
                    } else {
                        toVisit.addAll(c.children);
                    }
                }
                n.parent.children.remove(n);
            } else {
                tighten(n);
            }
            n = n.parent;
        }
        if (root.children.size() == 0) {
            root = buildRoot(true);
        } else if ((root.children.size() == 1) && (!root.leaf)) {
            root = root.children.get(0);
            root.parent = null;
        } else {
            tighten(root);
        }
        for (Node ne : q) {
            @SuppressWarnings("unchecked")
            Entry e = (Entry) ne;
            insert(e.coords, e.dimensions, e.entry);
        }
        size -= q.size();
    }

    /**
     * 清空整个R-Tree
     */
    public void clear() {
        root = buildRoot(true);
        //让GC做剩余的事情...
    }

    /**
     * 在RTree中插入数据entry, 和矩形匹配.
     * 
     * @param coords : 矩形的一个顶点(比如左上角)
     * @param dimensions : 矩形长度
     * @param entry : 待出入数据
     */
    public void insert(float[] coords, float[] dimensions, T entry) {
        assert (coords.length == D);
        assert (dimensions.length == D);
        Entry e = new Entry(coords, dimensions, entry);
        Node l = chooseLeaf(root, e);
        l.children.add(e);
        size++;
        e.parent = l;
        if (l.children.size() > M) {
            Node[] splits = splitNode(l);
            adjustTree(splits[0], splits[1]);
        } else {
            adjustTree(l, null);
        }
    }

    /**
     * Convenience method for inserting a point
     * 
     * @param coords
     * @param entry
     */
    public void insert(float[] coords, T entry) {
        insert(coords, pointDims, entry);
    }

    private void adjustTree(Node n, Node nn) {
        if (n == root) {
            if (nn != null) {
                // build new root and add children.
                root = buildRoot(false);
                root.children.add(n);
                n.parent = root;
                root.children.add(nn);
                nn.parent = root;
            }
            tighten(root);
            return;
        }
        tighten(n);
        if (nn != null) {
            tighten(nn);
            if (n.parent.children.size() > M) {
                Node[] splits = splitNode(n.parent);
                adjustTree(splits[0], splits[1]);
            }
        }
        if (n.parent != null) {
            adjustTree(n.parent, null);
        }
    }

    private Node[] splitNode(Node n) {
        // TODO: this class probably calls "tighten" a little too often.
        // For instance the call at the end of the "while (!cc.isEmpty())" loop
        // could be modified and inlined because it's only adjusting for the addition
        // of a single node. Left as-is for now for readability.
        @SuppressWarnings("unchecked")
        Node[] nn = new RTree.Node[] { n, new Node(n.coords, n.dimensions, n.leaf) };
        nn[1].parent = n.parent;
        if (nn[1].parent != null) {
            nn[1].parent.children.add(nn[1]);
        }
        LinkedList<Node> cc = new LinkedList<Node>(n.children);
        n.children.clear();
        Node[] ss = seedPicker == SeedPicker.LINEAR ? lPickSeeds(cc) : qPickSeeds(cc);
        nn[0].children.add(ss[0]);
        nn[1].children.add(ss[1]);
        tighten(nn);
        while (!cc.isEmpty()) {
            if ((nn[0].children.size() >= m) && (nn[1].children.size() + cc.size() == m)) {
                nn[1].children.addAll(cc);
                cc.clear();
                tighten(nn); // Not sure this is required.
                return nn;
            } else if ((nn[1].children.size() >= m) && (nn[0].children.size() + cc.size() == m)) {
                nn[0].children.addAll(cc);
                cc.clear();
                tighten(nn); // Not sure this is required.
                return nn;
            }
            Node c = seedPicker == SeedPicker.LINEAR ? lPickNext(cc) : qPickNext(cc, nn);
            Node preferred;
            float e0 = getRequiredExpansion(nn[0].coords, nn[0].dimensions, c);
            float e1 = getRequiredExpansion(nn[1].coords, nn[1].dimensions, c);
            if (e0 < e1) {
                preferred = nn[0];
            } else if (e0 > e1) {
                preferred = nn[1];
            } else {
                float a0 = getArea(nn[0].dimensions);
                float a1 = getArea(nn[1].dimensions);
                if (a0 < a1) {
                    preferred = nn[0];
                } else if (e0 > a1) {
                    preferred = nn[1];
                } else {
                    if (nn[0].children.size() < nn[1].children.size()) {
                        preferred = nn[0];
                    } else if (nn[0].children.size() > nn[1].children.size()) {
                        preferred = nn[1];
                    } else {
                        preferred = nn[(int) Math.round(Math.random())];
                    }
                }
            }
            preferred.children.add(c);
            tighten(preferred);
        }
        return nn;
    }

    // Implementation of Quadratic PickSeeds
    private RTree<T>.Node[] qPickSeeds(LinkedList<Node> nn) {
        @SuppressWarnings("unchecked")
        RTree<T>.Node[] bestPair = new RTree.Node[2];
        float maxWaste = -1.0f * Float.MAX_VALUE;
        for (Node n1 : nn) {
            for (Node n2 : nn) {
                if (n1 == n2)
                    continue;
                float n1a = getArea(n1.dimensions);
                float n2a = getArea(n2.dimensions);
                float ja = 1.0f;
                for (int i = 0; i < D; i++) {
                    float jc0 = Math.min(n1.coords[i], n2.coords[i]);
                    float jc1 = Math.max(n1.coords[i] + n1.dimensions[i], n2.coords[i] + n2.dimensions[i]);
                    ja *= (jc1 - jc0);
                }
                float waste = ja - n1a - n2a;
                if (waste > maxWaste) {
                    maxWaste = waste;
                    bestPair[0] = n1;
                    bestPair[1] = n2;
                }
            }
        }
        nn.remove(bestPair[0]);
        nn.remove(bestPair[1]);
        return bestPair;
    }

    /**
     * Implementation of QuadraticPickNext
     * 
     * @param cc the children to be divided between the new nodes, one item will be removed from this list.
     * @param nn the candidate nodes for the children to be added to.
     */
    private Node qPickNext(LinkedList<Node> cc, Node[] nn) {
        float maxDiff = -1.0f * Float.MAX_VALUE;
        Node nextC = null;
        for (Node c : cc) {
            float n0Exp = getRequiredExpansion(nn[0].coords, nn[0].dimensions, c);
            float n1Exp = getRequiredExpansion(nn[1].coords, nn[1].dimensions, c);
            float diff = Math.abs(n1Exp - n0Exp);
            if (diff > maxDiff) {
                maxDiff = diff;
                nextC = c;
            }
        }
        assert (nextC != null) : "No node selected from qPickNext";
        cc.remove(nextC);
        return nextC;
    }

    // Implementation of LinearPickSeeds
    private RTree<T>.Node[] lPickSeeds(LinkedList<Node> nn) {
        @SuppressWarnings("unchecked")
        RTree<T>.Node[] bestPair = new RTree.Node[2];
        boolean foundBestPair = false;
        float bestSep = 0.0f;
        for (int i = 0; i < D; i++) {
            float dimLb = Float.MAX_VALUE, dimMinUb = Float.MAX_VALUE;
            float dimUb = -1.0f * Float.MAX_VALUE, dimMaxLb = -1.0f * Float.MAX_VALUE;
            Node nMaxLb = null, nMinUb = null;
            for (Node n : nn) {
                if (n.coords[i] < dimLb) {
                    dimLb = n.coords[i];
                }
                if (n.dimensions[i] + n.coords[i] > dimUb) {
                    dimUb = n.dimensions[i] + n.coords[i];
                }
                if (n.coords[i] > dimMaxLb) {
                    dimMaxLb = n.coords[i];
                    nMaxLb = n;
                }
                if (n.dimensions[i] + n.coords[i] < dimMinUb) {
                    dimMinUb = n.dimensions[i] + n.coords[i];
                    nMinUb = n;
                }
            }
            float sep = (nMaxLb == nMinUb) ? -1.0f : Math.abs((dimMinUb - dimMaxLb) / (dimUb - dimLb));
            if (sep >= bestSep) {
                bestPair[0] = nMaxLb;
                bestPair[1] = nMinUb;
                bestSep = sep;
                foundBestPair = true;
            }
        }
        // In the degenerate case where all points are the same, the above
        // algorithm does not find a best pair. Just pick the first 2
        // children.
        if (!foundBestPair) {
            bestPair = new RTree.Node[] { nn.get(0), nn.get(1) };
        }
        nn.remove(bestPair[0]);
        nn.remove(bestPair[1]);
        return bestPair;
    }

    /**
     * Implementation of LinearPickNext
     * 
     * @param cc the children to be divided between the new nodes, one item will be removed from this list.
     */
    private Node lPickNext(LinkedList<Node> cc) {
        return cc.pop();
    }

    private void tighten(Node... nodes) {
        assert (nodes.length >= 1) : "Pass some nodes to tighten!";
        for (Node n : nodes) {
            assert (n.children.size() > 0) : "tighten() called on empty node!";
            float[] minCoords = new float[D];
            float[] maxCoords = new float[D];
            for (int i = 0; i < D; i++) {
                minCoords[i] = Float.MAX_VALUE;
                maxCoords[i] = Float.MIN_VALUE;

                for (Node c : n.children) {
                    // we may have bulk-added a bunch of children to a node (eg. in
                    // splitNode)
                    // so here we just enforce the child->parent relationship.
                    c.parent = n;
                    if (c.coords[i] < minCoords[i]) {
                        minCoords[i] = c.coords[i];
                    }
                    if ((c.coords[i] + c.dimensions[i]) > maxCoords[i]) {
                        maxCoords[i] = (c.coords[i] + c.dimensions[i]);
                    }
                }
            }
            for (int i = 0; i < D; i++) {
                // Convert max coords to dimensions
                maxCoords[i] -= minCoords[i];
            }
            System.arraycopy(minCoords, 0, n.coords, 0, D);
            System.arraycopy(maxCoords, 0, n.dimensions, 0, D);
        }
    }

    private RTree<T>.Node chooseLeaf(RTree<T>.Node n, RTree<T>.Entry e) {
        if (n.leaf) {
            return n;
        }
        float minInc = Float.MAX_VALUE;
        Node next = null;
        for (RTree<T>.Node c : n.children) {
            float inc = getRequiredExpansion(c.coords, c.dimensions, e);
            if (inc < minInc) {
                minInc = inc;
                next = c;
            } else if (inc == minInc) {
                float curArea = 1.0f;
                float thisArea = 1.0f;
                for (int i = 0; i < c.dimensions.length; i++) {
                    curArea *= next.dimensions[i];
                    thisArea *= c.dimensions[i];
                }
                if (thisArea < curArea) {
                    next = c;
                }
            }
        }
        return chooseLeaf(next, e);
    }

    /**
     * Returns the increase in area necessary for the given rectangle to cover the given entry.
     */
    private float getRequiredExpansion(float[] coords, float[] dimensions, Node e) {
        float area = getArea(dimensions);
        float[] deltas = new float[dimensions.length];
        for (int i = 0; i < deltas.length; i++) {
            if (coords[i] + dimensions[i] < e.coords[i] + e.dimensions[i]) {
                deltas[i] = e.coords[i] + e.dimensions[i] - coords[i] - dimensions[i];
            } else if (coords[i] + dimensions[i] > e.coords[i] + e.dimensions[i]) {
                deltas[i] = coords[i] - e.coords[i];
            }
        }
        float expanded = 1.0f;
        for (int i = 0; i < dimensions.length; i++) {
            expanded *= dimensions[i] + deltas[i];
        }
        return (expanded - area);
    }

    private float getArea(float[] dimensions) {
        float area = 1.0f;
        for (int i = 0; i < dimensions.length; i++) {
            area *= dimensions[i];
        }
        return area;
    }

    private boolean isOverlap(float[] scoords, float[] sdimensions, float[] coords, float[] dimensions) {
        final float FUDGE_FACTOR = 1.001f;
        for (int i = 0; i < scoords.length; i++) {
            boolean overlapInThisDimension = false;
            if (scoords[i] == coords[i]) {
                overlapInThisDimension = true;
            } else if (scoords[i] < coords[i]) {
                if (scoords[i] + FUDGE_FACTOR * sdimensions[i] >= coords[i]) {
                    overlapInThisDimension = true;
                }
            } else if (scoords[i] > coords[i]) {
                if (coords[i] + FUDGE_FACTOR * dimensions[i] >= scoords[i]) {
                    overlapInThisDimension = true;
                }
            }
            if (!overlapInThisDimension) {
                return false;
            }
        }
        return true;
    }

    /**
     * 节点
     */
    private class Node {
        /**
         * 高维矩形的一个定点,如左下角
         */
        final float[] coords;

        /**
         * 矩形的长度
         */
        final float[] dimensions;

        /**
         * 孩子节点
         */
        final LinkedList<Node> children;

        /**
         * 是否为叶子节点
         */
        final boolean leaf;

        /**
         * 父亲节点
         */
        Node parent;

        private Node(float[] coords, float[] dimensions, boolean leaf) {
            this.coords = new float[coords.length];
            this.dimensions = new float[dimensions.length];
            System.arraycopy(coords, 0, this.coords, 0, coords.length);
            System.arraycopy(dimensions, 0, this.dimensions, 0, dimensions.length);
            this.leaf = leaf;
            children = new LinkedList<Node>();
        }
    }

    /**
     * 实体,代表一个数据项
     * 注意:不是叶子节点,其父亲才是叶子节点
     */
    private class Entry extends Node {
        /**
         * 数据
         */
        final T entry;

        public Entry(float[] coords, float[] dimensions, T entry) {
            super(coords, dimensions, true);
            this.entry = entry;
        }

        public String toString() {
            return "Entry: " + entry;
        }
    }
}

参考

http://publib.boulder.ibm.com/infocenter/idshelp/v10/index.jsp?topic=/com.ibm.rtree.doc/rtree29.htm