# Lucene 6 基于BKD Tree Index 的应用

*作者： keehang 发布时间：2017-08-04*

BKD Tree

https://www.elastic.co/blog/lucene-points-6.0

Block k-d trees are a simple yet powerful data structure. At index time, they are built by recursively partitioning the full space of N-dimensional points to be indexed into smaller and smaller rectangular cells, splitting equally along the widest ranging dimension at each step of the recursion. However, unlike an ordinary k-d tree, a block k-d tree stops recursing once there are fewer than a pre-specified (1024 in our case, by default) number of points in the cell.

At that point, all points within that cell are written into one leaf block on disk and the starting file-pointer for that block is saved into an in-heap binary tree structure. In the 1D case, this is simply a full sort of all values, divided into adjacent leaf blocks. There are k-d tree variants that can support removing values, and rebalancing, but Lucene does not need these operations because of its write-once per-segment design.

At search time, the same recursion takes place, testing at each level whether the requested query shape intersects the left or right sub-tree of each dimensional split, and recursing if so. In the 1D case, the query shape is simply a numeric range whereas in the 2D and 3D cases, it is a geo-spatial shape (circle, ring, rectangle, polygon, cube, etc.).

1. General Multidimensional Space Points

Search for points with exact given values.

Search for points which has one of the value from a given set of values.

Search for points within a given range.

Get the number of points which has exact point.

Get the number of points within a given range. (Ranges are multidimensional ranges. In 3D, they are boxes.)

Divide points into range-buckets and get the count in each buckets. (Range bucket is a range which has a label in it)

2. Locations on the planet surface. (Latitude, Longitude)

Find closest set of airports to a given town.

Find the set of airports within a given radius from a particular town.

Find the set of airports inside a country. (Country can be given as a polygon)

Find the set of airports within a given range of Latitudes and Longitudes. It is a Latitude, Longitude box query. (For a examples: Airports closer to the equatorial)

Find the set of airports closer to a given path. (Path can be something like a road. Find the airports which are less than 50km away from a given highway)

Count the airports in each country by giving country maps as polygons.

Loading Data is finished ----------------------------------------------------------------------

建索引花费时间：982ms

LatLon - Box Query Example------------------------------------------------------------------------------

search_LatLon_Box 花费时间：69ms

LatLon - K Nearest------------------------------------------------------------------------------

search_LatLon_Nearest 花费时间：108ms

DoublePoint 1D Point Exact------------------------------------------------------------------------------

search_Double_1D_Exact 花费时间：10ms

DoublePoint 1D - Range------------------------------------------------------------------------------

search_Double_1D_range 花费时间：8ms

DoublePoint 1D - Range Buckets -----------------------------------------------------------------------------

search_Double_1D_range_bucket 花费时间：58ms

DoublePoint multi dimensional - Range------------------------------------------------------------------------------

search_Double_MiltiDimensional_Range 花费时间：1ms

https://www.elastic.co/blog/lucene-points-6.0

Block k-d trees are a simple yet powerful data structure. At index time, they are built by recursively partitioning the full space of N-dimensional points to be indexed into smaller and smaller rectangular cells, splitting equally along the widest ranging dimension at each step of the recursion. However, unlike an ordinary k-d tree, a block k-d tree stops recursing once there are fewer than a pre-specified (1024 in our case, by default) number of points in the cell.

At that point, all points within that cell are written into one leaf block on disk and the starting file-pointer for that block is saved into an in-heap binary tree structure. In the 1D case, this is simply a full sort of all values, divided into adjacent leaf blocks. There are k-d tree variants that can support removing values, and rebalancing, but Lucene does not need these operations because of its write-once per-segment design.

At search time, the same recursion takes place, testing at each level whether the requested query shape intersects the left or right sub-tree of each dimensional split, and recursing if so. In the 1D case, the query shape is simply a numeric range whereas in the 2D and 3D cases, it is a geo-spatial shape (circle, ring, rectangle, polygon, cube, etc.).

`测试集合：模拟一亿条`

0," nnrIuS","raet","lnsr","inu ","saia",83.405273,73.302012,3991,24,"N"," usA","airport","rra i"

1,"omlritp","aaVe","y Mu","AaVV","NMc ",15.459643,-20.826241,2627,54,"a","eemo","airport","MaArp"

2,"kyaneMr","iasm","raAA"," tnt","inls",16.606066,38.663728,2761,53,"o","arIi","airport","uiron"

1. General Multidimensional Space Points

Search for points with exact given values.

Search for points which has one of the value from a given set of values.

Search for points within a given range.

Get the number of points which has exact point.

Get the number of points within a given range. (Ranges are multidimensional ranges. In 3D, they are boxes.)

Divide points into range-buckets and get the count in each buckets. (Range bucket is a range which has a label in it)

2. Locations on the planet surface. (Latitude, Longitude)

Find closest set of airports to a given town.

Find the set of airports within a given radius from a particular town.

Find the set of airports inside a country. (Country can be given as a polygon)

Find the set of airports within a given range of Latitudes and Longitudes. It is a Latitude, Longitude box query. (For a examples: Airports closer to the equatorial)

Find the set of airports closer to a given path. (Path can be something like a road. Find the airports which are less than 50km away from a given highway)

Count the airports in each country by giving country maps as polygons.

**search result:**Loading Data is finished ----------------------------------------------------------------------

建索引花费时间：982ms

LatLon - Box Query Example------------------------------------------------------------------------------

search_LatLon_Box 花费时间：69ms

LatLon - K Nearest------------------------------------------------------------------------------

search_LatLon_Nearest 花费时间：108ms

DoublePoint 1D Point Exact------------------------------------------------------------------------------

search_Double_1D_Exact 花费时间：10ms

DoublePoint 1D - Range------------------------------------------------------------------------------

search_Double_1D_range 花费时间：8ms

DoublePoint 1D - Range Buckets -----------------------------------------------------------------------------

search_Double_1D_range_bucket 花费时间：58ms

DoublePoint multi dimensional - Range------------------------------------------------------------------------------

search_Double_MiltiDimensional_Range 花费时间：1ms