実装またはアルゴリズム？
ネイティブオプションを軽視せずに、実装ではなくアルゴリズムを比較してみましょう。 現在のアルゴリズムは、データベースバージョンの2つの列と、ネイティブの範囲境界を使用します。 しかし、範囲を保存せず、開始点のみを保存するとどうなりますか？ 同様のアイデアは 、記事へのコメントで既に述べられています。「...すべてを保存する必要はなく、範囲の終わりだけを保存する必要があります...」 実際、この場合、検索は明らかに半分に加速されます。値が含まれる範囲の先頭のみを見つける必要があります。 空の範囲があることに気づいた人には、それらを保存できると答えます：voidの始まりとそれを象徴する値。
単純な範囲またはネスト？
前の例で検討した例では、単純な意見では、 GeoLite Countryが使用されました。GeoLiteCountryでは、範囲が重複せず、ネストされた範囲の問題はありません。 たとえばロシアのIpGeoBaseなどのより複雑なケースでは、範囲が容赦なく交差し、 startとendの間にneedleのような単純なクエリでは対応できません。 しかし、私たちを助けるために、検索アルゴリズムを使いこなすだけです！
フラットレンジコンセプト
データベースを使用した例を使用して、フラット範囲の概念を見て比較してみましょう。 また、簡単にするために、値のリストではなく、一度に1つの値を検索するオプションを検討します。 サブタイトルが質問になり、リストの2つの要素が通常範囲とフラット範囲の回答になります。
これは何ですか
- 3つの列： 開始、終了、値
- 2列： 開始、値
空の範囲はどのようにカウントされますか？
- 方法はありません-単純な範囲では、空の範囲のリクエストの場合、ゼロのレコードが返されるため、それらを考慮する必要はありません。
- 空の範囲の先頭は開始列に格納され、特定の無効な指定は値列に格納されます。NULLにすることもできますが、 startとvalueで複合主キーを使用する場合は0にすることもできます 。
あと何レコードありますか？
- GeoLiteCountry-160222のような単純な場合。
IpGeoBaseのような複雑な-39449。
以前の形式の複雑で古いタイプのIpGeoBaseでは、多くの連続した範囲があります（たとえば、2011年11月から）-148666。 - GeoLiteCountry-161619。1％未満の増加。
IpGeoBase-46047。わずか16％の増加。
前の形式のIpGeoBase-31156。最大80％減少します。
それを探す方法は？
- 単純な場合： 開始と終了の制限の間の針1 。
困難な状況では、ネストがある場合、追加のdiff列を接続する必要があります。これは、複合インデックスで使用され、その結果、開始と終了の間の針、終了順、差分制限1のような恐怖が生じます。 - いずれの場合も簡単です： neddle> = start desc limit by start desc limit 1 。
DBまたは他の検索プロバイダーは何をする必要がありますか？
- 最初に、ある方向に進み、次にすべてが別の方向から正常であることを確認します。 つまり 通常、2つの動きをします。
- 常に同じ方向に進んでください。
入手方法
- すでにあります-geoip範囲を持つファイルからのダウンロード。
- 3列のテーブルを用意し、特別なストリートマジックを使用して、3列のテーブルに変換します。 付録1を参照してください 。
おわりに
もちろん、あなたは尋ねます-どのようにデータをフラットビューに変換し、どのくらい増加しますか？ 最後から回答します。ボリュームは約2倍に増加し、コメント付きのSQL変換を以下にレイアウトします（ 付録1を参照）。
PS：最も可能性が高いのは、ネイティブバージョンでフラットレンジの概念を適用すると、すべてが瞬時にさらに宇宙的になることです。 確認できる人への要求は、この声明を確認することです。
PS2： IPv6がよりアクティブな時代に、HUGEINTがそれまでに配布されない場合、ストレージがCHARの形式である場合、フラット範囲も非常に役立つこともわかります。
付録1. MySQLを例として使用してフラット範囲を作成する
github.com/garex/geoip-flat-range 、つまりgithub.com/garex/geoip-flat-range/blob/master/01-create-flat-range-mysql.sqlから取得
-- Create intermediate table with 3 columns -- Change this to your columns and/or table drop table if exists t3; create table t3 select range_start f, range_end t, country_code v from countries_ips ; alter table t3 add primary key (f,t,v); -- Create target table with 2 columns and fill it with all distinct ranges borders drop table if exists t2; create table t2 select distinct border as f, (select max(v) from t3) as v from ( select f-1 as border from t3 union select f from t3 union select t from t3 union select t+1 from t3 ) inn order by f; -- Here we just reset value column as it was filled by max value to have auto created column with needed type update t2 set v = null; -- We can add PK here, as all our range borders are unique alter table t2 add primary key(f); -- Adding diff column, that will help us to order ranges during main update alter table t3 add column diff int(10) unsigned, add unique index dif_f(diff, f); update t3 set diff = tf; -- Create helper table, that will help to smooth main update drop table if exists t3diff; create table t3diff select distinct diff from t3 order by diff; -- Here are our MAIN update update t3diff, t2, t3 set t2.v = t3.v where t3.diff = t3diff.diff and t2.f between t3.f and t3.t; -- We dont' need 'em anymore drop table if exists t3; drop table if exists t3diff; -- We should remove records, that points to the same value and is one after another alter table t2 drop primary key; alter table t2 add column row_number int(10) unsigned not null auto_increment primary key; alter table t2 add column next_row_number int(10) unsigned not null; update t2 set next_row_number = row_number + 1; alter table t2 add unique index next_row_number_v (next_row_number, v); delete t2.* from t2, ( select cur.row_number from t2 as cur join t2 prev on cur.row_number = prev.next_row_number and cur.v = prev.v ) as inn where t2.row_number = inn.row_number; -- Also we dont' need first record delete from t2 where row_number = 1; -- Removing extra columns, that will not help us anymore -- And also adding primary key on key and value to just always use index instead of table alter table t2 drop column row_number, drop column next_row_number, drop primary key, drop index next_row_number_v, add primary key (f, v) ; -- ... And renaming target table to more human readable form -- Change table`s/columns` names/definitions to your tables/columns drop table if exists countries_ips_flat; alter table t2 rename to countries_ips_flat, change column f range_start int(20) unsigned not null default 0 first, change column v country_code varchar(2) not null default '' after range_start; -- Comparing records count and check, that's all is ok select (select count(*) from countries_ips) as default_range_records, (select count(*) from countries_ips_flat) as flat_range_records;