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.
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
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
[尊重社区原创，转载请保留或注明出处]
本文地址：http://searchkit.cn/article/211
本文地址：http://searchkit.cn/article/211
