Attached patches add SP-GiST support to the inet datatypes. The operator class comes with a small change on the SP-GiST framework to allow fixed number of child nodes.
The index is like prefix tree except that it doesn't bother to split the addresses into parts as text is split. It also doesn't use labels to know the part after the prefix, but relies on static node numbers.
The GiST index released with version 9.4 performs really bad with real world data. SP-GiST works much better with the query posted to the performance list [1] a while ago:
> hasegeli=# SELECT DISTINCT route INTO hmm FROM routes_view WHERE asn = 2914;
> SELECT 732
>
> hasegeli=# EXPLAIN ANALYZE SELECT routes.route FROM routes JOIN hmm ON routes.route && hmm.route;
> QUERY PLAN
> ----------------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=0.41..571742.27 rows=2248 width=7) (actual time=12.643..20474.813 rows=8127 loops=1)
> -> Seq Scan on hmm (cost=0.00..11.32 rows=732 width=7) (actual time=0.017..0.524 rows=732 loops=1)
> -> Index Only Scan using route_gist on routes (cost=0.41..552.05 rows=22900 width=7) (actual time=4.851..27.948 rows=11 loops=732)
> Index Cond: (route && (hmm.route)::inet)
> Heap Fetches: 8127
> Planning time: 1.507 ms
> Execution time: 20475.605 ms
> (7 rows)
>
> hasegeli=# DROP INDEX route_gist;
> DROP INDEX
>
> hasegeli=# CREATE INDEX route_spgist ON routes USING spgist (route);
> CREATE INDEX
>
> hasegeli=# EXPLAIN ANALYZE SELECT routes.route FROM routes JOIN hmm ON routes.route && hmm.route;
> QUERY PLAN
> -----------------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=0.41..588634.27 rows=2248 width=7) (actual time=0.081..16.961 rows=8127 loops=1)
> -> Seq Scan on hmm (cost=0.00..11.32 rows=732 width=7) (actual time=0.022..0.079 rows=732 loops=1)
> -> Index Only Scan using route_spgist on routes (cost=0.41..575.13 rows=22900 width=7) (actual time=0.014..0.021 rows=11 loops=732)
> Index Cond: (route && (hmm.route)::inet)
> Heap Fetches: 8127
> Planning time: 1.376 ms
> Execution time: 15.936 ms